二叉树，永远的神。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if len(preorder) == 0:
return None
root = TreeNode(preorder[0])
root_index = inorder.index(root.val)
left_inorder = inorder[:root_index]
right_inorder = inorder[root_index+1:]
left_preorder = preorder[1:1+len(left_inorder)]
right_preorder = preorder[1+len(left_inorder):]
root.left = self.buildTree(left_preorder, left_inorder)
root.right = self.buildTree(right_preorder, right_inorder)
return root
|
序列化和反序列化二叉树步骤之一，通过前序遍历和中序遍历构造二叉树。要点在于通过前序序列知道根节点，通过中序序列知道左子树和右子树是哪些。
边界点：递归约束，叶节点的子节点None停止递归，通过判断preorder是否为空判断该节点是否为None。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return check(root.left, root.right);
}
private boolean check(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
return (p.val == q.val) && check(p.left, q.right) && check(p.right, q.left);
}
}
|
时间复杂度：O(N)
空间复杂度：O(N) 原因在于虽然我们只需要递归O(logN)层但是我们每层都要创建2个栈空间，所以我们的空间复杂度为O(2logN)=O(N)
难点：注意镜像，所以我们需要 check(p.left, q.right) && check(p.right, q.left);
题目简单，但是LC给的边界值实在恶心。
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public boolean isValidBST(TreeNode root) {
return verify(root, null, null);
}
public boolean verify(TreeNode root, TreeNode maximum, TreeNode minimum) {
if (root == null) { return true; }
if (maximum != null && root.val >= maximum.val) { return false; }
if (minimum != null && root.val <= minimum.val) { return false; }
return verify(root.left, root, minimum) && verify(root.right, maximum, root);
}
}
|
解决边界值问题可以用Long.MAX_VALUE来代替Integer.MAX_VALUE , 或者就像labuladong这样传递节点而不是边界值，至于为什么传递节点，因为null是不可以转换为int的。该问题的主要关键点在于bst的性质在于左子树全点小于父节点而不是左子点小于父节点。
完全二叉树的节点数
普通二叉树：
1
2
3
4
| public int countNodes(TreeNode root) {
if (root == null) return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}
|
满二叉树：
1
2
3
4
5
6
7
8
| public int countNodes(TreeNode root) {
int h = 0;
while (root != null) {
root = root.left;
h++;
}
return (int)Math.pow(2, h)-1;
}
|
完全二叉树：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public int countNodes(TreeNode root) {
if (root == null) { return 0; }
int h_left = 0, h_right = 0;
TreeNode left = root, right = root;
while (left != null) {
left = left.left;
h_left++;
}
while (right != null) {
right = right.right;
h_right++;
}
if (h_left == h_right) {
return (int)Math.pow(2, h_left)-1;
}
return countNodes(root.left)+countNodes(root.right)+1;
}
|
时间复杂度: O(log(N)∗log(N))
原因: 一棵完全二叉树的左子树和右子树中至少有一棵是满二叉树
算法的递归深度就是树的高度O(logN)，每次递归所花费的时间就是 while 循环，需要O(logN)，所以总体的时间复杂度是O(logN∗logN)。