Leetcode practice by java,c,c++,python,scala
1.两个链表的第一个公共结点
2.从尾到头打印链表
3.删除链表中重复的结点
4.反转链表
5.合并两个排序的链表
6.复杂链表的复制
7.链表中倒数第k个结点
8.链表中环的入口结点
9.二叉树中和为某一值的路径
10.二叉树的下一个结点
11.二叉树的前序遍历
12.二叉树的深度
13.二叉树的镜像
14.从上往下打印二叉树
15.对称的二叉树
16.序列化二叉树
17.把二叉树打印成多行
18.按之子顺序打印二叉树
19.树的子结构
20.重建二叉树
21.二叉搜索树与双向链表
22.二叉搜索树的后序遍历序列
解法一：递归
根据二叉搜索树的定义，可以通过递归，判断所有子树的正确性（即其后续遍历是否满足二叉
搜索树的定义），若所有子树都正确，则此序列为二叉搜索树的后序遍历。
- 终止条件：当$i >= j$,说明此子树结点数量<=1,无需判别正确性，因此直接返回true；
- 递推工作：
- 划分左右子树：遍历后序遍历的[i,j]区间元素，寻找第一个大于根节点的结点， 索引记为m。此时，可划分出左子树区间[i, m-1]、右子树区间[m, j-1]、根结点索引$j$。
- 判断是否为二叉搜索树：
- 左子树区间[i,m-1]内的所有结点都应<postorder[j]。而第
1.划分左右子树步骤 已经保证左子树区间的正确性，因此只需要判断右子树区间即可。 - 右子树区间[m, j-1]内的所有结点都应>postorder[j]。实现方式为遍历，当遇到 <=postorder[j]的结点则跳出；则可通过p=j判断是否为二叉搜索树。
- 左子树区间[i,m-1]内的所有结点都应<postorder[j]。而第
- 返回值：所有子树都需正确才可判定正确，因此使用与逻辑&&连接。
- p=j:判断此树是否正确。
- recur(i, m-1):判断此树的左子树是否正确。
- recur(m, j-1):判断此树的右子树是否正确。
- 复杂度分析：
- 时间复杂度$O(N^2)$:每次调用recur(i,j)减去一个根结点，因此递归占用$O(N)$； 最差情况下（即当树退化为链表），每轮递归都需遍历树所有结点，占用$O(N)$。
- 空间复杂度$O(N)$:最差情况下（即当树退化为链表），递归深度将达到$N$。
class Solution:
def verifyPostorder(self, postorder:[int]) -> bool:
def recur(i, j):
if i >= j:
return True
p = i
while postorder[p] < postorder[j]:
p += 1
m = p
while postorder[p] > postorder[j]:
p += 1
return p == j and recur(i, m-1) and recur(m, j-1)
return recur(0, len(postorder) - 1)23.二叉搜索树的第k个结点
24.二维数组中的查找
25.把数组排成最小的数
26.数字在排序数组中出现的次数
27.数组中出现次数超过一半的数字
28.数组中只出现一次的数字
29.数组中的逆序对
30.数组中重复的数字
31.旋转数组的最小数字
32.构建乘积数组
33.调整数组顺序使奇数位于偶数前面
34.连续子数组的最大和
35.字符串的排列
36.左旋转字符串
37.把字符串转换成整数
38.替换空格
39.正则表达式匹配
40.第一个只出现一次的字符
41.翻转单词顺序序列
42.表示数值的字符串