Refresh - 树
从树的角度，再来看看dfs和bfs。
树的bfs
bfs更适用于层级关系的解法。比如求树某一层的深度（不是高度）；涉及到二叉树的堂兄弟节点等。
如果给出树的层序遍历，然后让构建一棵树，那么显然也应该使用bfs。示例输入：20,null,40,34,70,21,null,55,78
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.util.*;
public class Main {
public static void main(String... args) {
Scanner sc = new Scanner(System.in);
String[] tokens = sc.nextLine().split(",");
Main main = new Main();
TreeNode root = main.build(tokens);
System.out.println(main.isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE));
}
private boolean isBST(TreeNode root, int min, int max) {
if (root == null) {
return true;
}
if (root.value > max || root.value < min) {
return false;
}
return isBST(root.left, min, root.value) && isBST(root.right, root.value, max);
}
private TreeNode build(String[] tokens) {
Queue<TreeNode> queue = new ArrayDeque<>();
int i = 0;
if (isNull(tokens[0])) {
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
TreeNode cur = queue.poll();
i++;
// 注意数组越界。叶子结点是没有子节点的，此时i越界了
if (i < tokens.length && !isNull(tokens[i])) {
TreeNode left = new TreeNode(Integer.parseInt(tokens[i]));
cur.left = left;
queue.add(left);
}
i++;
if (i < tokens.length && !isNull(tokens[i])) {
TreeNode right = new TreeNode(Integer.parseInt(tokens[i]));
cur.right = right;
queue.add(right);
}
}
}
return root;
}
private boolean isNull(String val) {
return "null".equals(val);
}
public static class TreeNode {
int value;
TreeNode left, right;
TreeNode(int value) {
this.value = value;
}
}
}
树的DFS
树的DFS只是DFS的一个特例。
当掌握了dfs，甚至总结出了dfs的模板的时候，就会发现树的dfs只是dfs这个模板下的一个很小的特例：一个每次仅有两个选择的dfs而已。所以在这个模板里用不到for循环去试探每一种情况，只需要把两种情况都写出来就行了！
1
2
3
4
5
6
7
8
9
void dfs(TreeNode root) {
// 终结条件？
// dfs选择1
dfs(root.left);
// 回溯，再dfs选择2
dfs(root.right);
// 又回溯
}
这个时候再看写树算法的套路框架，就显得很容易了。牢记这一点：树的dfs就是dfs的一种只有两种选择的特例而已。
当时我看到上述模板在讨论验证BST时，很喜欢一个观点：
出现错误，不要慌张，框架没有错，一定是某个细节问题没注意到。我们重新看一下 BST 的定义，root 需要做的不只是和左右子节点比较，而是要整个左子树和右子树所有节点比较。怎么办，鞭长莫及啊！这种情况，我们可以使用辅助函数，增加函数参数列表，在参数中携带额外信息。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public boolean isValidBST(TreeNode root) {
// 竟然卡int的边界值……
return inBoundary(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean inBoundary(TreeNode root, long low, long high) {
if (root == null) {
return true;
}
// woc, BST的定义是左子树必须都小于跟，而不是小于等于；右侧同理
if (root.val <= low || root.val >= high) {
return false;
}
return inBoundary(root.left, low, root.val) && inBoundary(root.right, root.val, high);
}
}
但是当我们意识到树的dfs只是“dfs的一种只有两种选择的特例而已”的时候，就会觉得这句话也不过如此了，毕竟在讨论通用dfs的时候就发现了，选择什么作为参数列表，本来就是根据需要来的。所以这里给函数加个min/max，很稀松平常，需要就加呗。
但是以前没把树的dfs和通用dfs紧密联系起来的时候，只是记住了树的dfs的大致样子，导致每次看到给树的dfs加参数的操作，总觉得很精妙。现在看来不过如此。
再举一个类似的例子：路径总和，当前路径的sum是要一路传下去的。这和上面的组合总和II一样，参数列表里要加个参数把当前遍历到的元素的sum传下去而已。
二叉搜索树BST的DFS：做了剪枝的DFS
既然树的dfs是dfs的特例，那么bst的dfs更是特例中的特例。
此时再看bfs的查找算法，就是一个加上了限制条件的回溯。其实就是相当于我们拿bst固有的节点大小特性来给普通dfs做了剪枝：
1
2
3
4
5
6
7
8
9
boolean isInBST(TreeNode root, int target) {
if (root == null) return false;
if (root.val == target)
return true;
if (root.val < target)
return isInBST(root.right, target);
if (root.val > target)
return isInBST(root.left, target);
}
没利用上bst的大小关系，写出来的就是没剪枝的dfs，普通二叉树的dfs：
1
2
3
4
5
6
7
boolean isInBST(TreeNode root, int target) {
if (root == null) return false;
if (root.val == target) return true;
return isInBST(root.left, target)
|| isInBST(root.right, target);
}
DFS结果的收集方式
之前的通用dfs模板讨论主要讨论了：
- 终结条件
- 情况选择
- 剪枝
- 参数列表
但其实还有一个比较重要的考量：返回类型。通用dfs里，一般求的是结果集，所以通过把result list作为参数传入下一层dfs去收集结果，此时返回值只需要设为null。
但是树和图不一定是这样：
- 求的是一个数：
- 岛屿周长/面积：各个方向（4个方向）上的值累加起来即可；
- 数的叶子结点个数：每个方向（左、右）的叶子加起来即可；
- 数的高度：每个方向的高度的max；
虽然只要传入一个类似atomic integer的参数就和传入result list一样了，但是更优雅的方式应该是让dfs return一个数，然后reduce（累加/max等）
- 求的是一棵树。比如下面的题。
比如bst中插入一个数。从通用dfs的角度来看，就是在思考它怎么转化为一个dfs的问题？dfs到一个null节点的时候，就是可以插入的地方。返回的是root，所以我们在dfs的时候把root类比为result list的角色，把它作为参数传进dfs函数，最后返回root就行了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
dfs(root, val);
return root;
}
// 以通用dfs的思路去插入bst，此时root相当于result，是结果收集者
void dfs(TreeNode root, int val) {
if (val < root.val) {
if (root.left == null) {
root.left = new TreeNode(val);
} else {
dfs(root.left, val);
}
}
if (val > root.val) {
if (root.right == null) {
root.right = new TreeNode(val);
} else {
dfs(root.right, val);
}
}
}
}
null情况在进入dfs之前去处理，dfs函数本身不处理null。
以通用dfs的思维去思考，非常简单！但是和上面“求的是一个数”的例子类似，这样写稍显啰嗦，我还是推荐尝试优化一下返回值，至少对思维训练很有帮助！
由于返回的是单元素TreeNode（类似单元素int），我们应该像直接renturn int，最后再去reduce一样，考虑return TreeNode。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
TreeNode insertIntoBST(TreeNode root, int val) {
// 找到空位置插入新节点
if (root == null) return new TreeNode(val);
// if (root.val == val)
// BST 中一般不会插入已存在的元素
if (root.val < val)
root.right = insertIntoBST(root.right, val);
if (root.val > val)
root.left = insertIntoBST(root.left, val);
return root;
}
确实困难很多。
另一个角度就是记住bst的模板。虽然从抽象的角度认识到它只是通用bfs的一个特例对理解它很有帮助，但是记住这个特例模板也非常重要——BST 中的遍历框架，就是“找”的问题。直接套框架，加上“改”的操作即可。一旦涉及“改”，函数就要返回 TreeNode 类型，并且对递归调用的返回值进行接收。
认识到它符合抽象性，同时记住它有独特性。
左右子树组合/切分
悟了上面这一点，就能写出前序+中序构造二叉树、中序+后续构造二叉树，虽然它不是bst，但是用了上面左右子树切分、组合的思想：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, 0, inorder, 0, preorder.length - 1);
}
// 每当需要二分的时候，用左右start、end就行了
// preorder只判断root
// inorder才是做左右切分的那个，所以start、end代表的是inorder的下标
private TreeNode build(int[] preorder, int rootIndexInPreorder, int[] inorder, int start, int end) {
if (start > end) {
return null;
}
int rootVal = preorder[rootIndexInPreorder];
TreeNode root = new TreeNode(rootVal);
int rootIndexInInorder = -1;
for (int i = start; i <= end; i++) {
if (inorder[i] == rootVal) {
rootIndexInInorder = i;
break;
}
}
int leftSize = rootIndexInInorder - start;
// 左边是inorder数组里的start ~ rootIndexInInorder - 1，左边的root是preorder里的rootIndexInPreorder+1的那个
// 右边是inorder数组里的rootIndexInInorder + 1 ~ end，右边的的root是preorder里的rootIndexInPreorder+leftSize+1的那个
root.left = build(preorder, rootIndexInPreorder + 1, inorder, start, rootIndexInInorder - 1);
root.right = build(preorder, rootIndexInPreorder + leftSize + 1, inorder, rootIndexInInorder + 1, end);
return root;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return build(postorder, postorder.length - 1, inorder, 0, inorder.length - 1);
}
private TreeNode build(int[] postorder, int rootIndexInPostOrder, int[] inorder, int start, int end) {
if (start > end) {
return null;
}
int rootVal = postorder[rootIndexInPostOrder];
TreeNode root = new TreeNode(rootVal);
int rootIndexInInorder = -1;
for (int i = end; i >= start; i--) {
if (inorder[i] == rootVal) {
rootIndexInInorder = i;
break;
}
}
int rightSize = end - rootIndexInInorder;
root.right = build(postorder, rootIndexInPostOrder - 1, inorder, rootIndexInInorder + 1, end);
root.left = build(postorder, rootIndexInPostOrder - rightSize - 1, inorder, start, rootIndexInInorder - 1);
return root;
}
}
包括有序数组构造为BST（分治）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return build(nums, 0, nums.length - 1);
}
private TreeNode build(int[] nums, int start, int end) {
if (start > end) {
return null;
}
int mid = (start + end) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = build(nums, start, mid - 1);
root.right = build(nums, mid + 1, end);
return root;
}
}
最好是左闭右开：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
// 左闭右开
return divide(nums, 0, nums.length);
}
private TreeNode divide(int[] nums, int left, int right) {
if (left >= right) {
return null;
}
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(nums[mid]);
// 左闭右开
root.left = divide(nums, left, mid);
// 左闭右开
root.right = divide(nums, mid + 1, right);
return root;
}
}
和麻烦点儿的有序链表构造为BST：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public TreeNode sortedListToBST(ListNode head) {
return divide(head, null);
}
private TreeNode divide(ListNode head, ListNode end) {
// 这个算防止一开始为null吧
if (head == null) {
return null;
}
// 退出条件
if (head == end) {
return null;
}
ListNode mid = findMid(head, end);
TreeNode root = new TreeNode(mid.val);
root.left = divide(head, mid);
// 这个必须是mid+1，因为mid已经用过了
root.right = divide(mid.next, end);
return root;
}
private ListNode findMid(ListNode head, ListNode end) {
ListNode fast = head, slow = head;
while (fast != end && fast.next != end) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
官方的题解也不错，很精髓：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public TreeNode sortedListToBST(ListNode head) {
return buildTree(head, null);
}
public TreeNode buildTree(ListNode left, ListNode right) {
if (left == right) {
return null;
}
ListNode mid = getMedian(left, right);
TreeNode root = new TreeNode(mid.val);
root.left = buildTree(left, mid);
root.right = buildTree(mid.next, right);
return root;
}
public ListNode getMedian(ListNode left, ListNode right) {
ListNode fast = left;
ListNode slow = left;
while (fast != right && fast.next != right) {
fast = fast.next;
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
同样是有序数组，95. 不同的二叉搜索树 II没要求平衡，所以就可以以任意节点作为root。它的思维比上面又多套了一层，核心是以当前每一个点作为root：
- 数组分两段，当前pivot是root，左边是左子树，右边是右子树；
- 最后两边的合法子树全排列一下就行了……
只能说想不来，照葫芦画瓢吧：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public List<TreeNode> generateTrees(int n) {
return build(1, n + 1);
}
private List<TreeNode> build(int start, int end) {
if (start >= end) {
// 这个null是必须的，比如左子树为null可以和每一种右子树组成一棵树
// 但是如果没这个null，下面的双重遍历就没了
List<TreeNode> result = new ArrayList<>();
result.add(null);
return result;
// 会NPE，所以只能用上面的写法
// return List.of(null);
}
List<TreeNode> result = new ArrayList<>();
// 以这一棵子树（这一段）的任意一个数字i作为root，排列组合一下
for (int i = start; i < end; i++) {
List<TreeNode> lefts = build(start, i);
List<TreeNode> rights = build(i + 1, end);
for (TreeNode l : lefts) {
for (TreeNode r : rights) {
TreeNode root = new TreeNode(i);
root.left = l;
root.right = r;
result.add(root);
}
}
}
return result;
}
}
注意这个return null，null是一棵子树。
894. 所有可能的真二叉树和这个思想类似，不过更简单一些，因为任何一边都不可能为null，必须是奇数个节点。其他部分都一样：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public List<TreeNode> allPossibleFBT(int n) {
return build(n);
}
private List<TreeNode> build(int cur) {
if (cur == 1) {
return List.of(new TreeNode(0));
}
List<TreeNode> result = new ArrayList<>();
// 当前要消耗掉一个节点，剩下cur-1个
cur--;
for (int i = 1; i < cur; i += 2) {
List<TreeNode> lefts = build(i);
List<TreeNode> rights = build(cur - i);
for (TreeNode l : lefts) {
for (TreeNode r :rights) {
TreeNode root = new TreeNode(0);
root.left = l;
root.right = r;
result.add(root);
}
}
}
return result;
}
}
还真想出来了:D
241. 为运算表达式设计优先级，一模一样的思路，这里可以把符号看作root，组成一棵树，就和上面的两道题一模一样了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public List<Integer> diffWaysToCompute(String expression) {
return build(expression);
}
private List<Integer> build(String exp) {
int expNumber = number(exp);
if (expNumber != -1) {
// 当前子树是一个纯数字
return List.of(expNumber);
}
List<Integer> result = new ArrayList<>();
for (int i = 0; i < exp.length(); i++) {
char c = exp.charAt(i);
// 以每一个符号作为二叉树的root，分别求左右分支
if (c == '+' || c == '-' || c == '*') {
List<Integer> lefts = build(exp.substring(0, i));
List<Integer> rights = build(exp.substring(i + 1, exp.length()));
for (int l : lefts) {
for (int r :rights) {
int ans = c == '+' ? l + r :
c == '-' ? l - r : l * r;
result.add(ans);
}
}
}
}
return result;
}
private int number(String exp) {
int sum = 0;
for (char c : exp.toCharArray()) {
if (!Character.isDigit(c)) {
return -1;
}
sum = sum * 10 + (c - '0');
}
return sum;
}
}
最后还想提一下96. 不同的二叉搜索树，它和95. 不同的二叉搜索树 II的区别在于后者需要列出所有的情况，前者却只需要一个数字（有多少种情况）。而且这道题给出的n明显比后者大一些，说明再用这种组合分治的思想会超时。仔细想想，不同的情况下其实里面有很多重复子问题，有重复构建子树的情况，所以这道题需要用动态规划。
“需要用”的意思是可以不用，可以不用的意思是得会上面的分治。也就是说，无论如何，得先学会上面这个分治的思路。在此基础上，因为分治有重复子问题，且这道题要的只是一个数字，所以可以用动态规划来解决。
然后就会发现，经常说动态规划的重点是转移方程，但转移方程只是使用动态规划后的一个捷径计算，重点是脑子里要有问题本身的解决思路，知道哪一种情况是由哪几种情况组合出来的，这是问题的本质解决思路。在此基础上，如果用了动态规划，这个思路就是转移方程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
// init
dp[0] = 1; // 空子树也是一种情况
dp[1] = 1;
// dp[2] = 2;
// transfer
// 枚举每一种n对应的结果
for (int i = 2; i <= n; i++) {
// 当前root用一个，所以还剩i-1个
int nodes = i - 1;
int sum = 0;
// left最少用0个节点，最多可以占用所有的nodes
for (int left = 0; left <= nodes; left++) {
int right = nodes - left;
sum += dp[left] * dp[right];
}
dp[i] = sum;
}
return dp[n];
}
}
所以说，动态规划的题目是和问题本身的解决思路高度相关的。在原有思路的基础上，才是考虑怎么把它转成动态规划的形式，也就是怎么复用记忆图来省去没必要的计算。
路径问题
所用到的方法还是之前总结的通用dfs模板。但是需要注意，虽然都是dfs，但是对于树来说有前序遍历、后续遍历，不同的处理方式适合不同的题型。前序遍历适合自顶向下，因为它先处理root。逻辑上从上到下的题目都是前序遍历。比如路径总和 II、二叉树的所有路径。
但是有时候从下到上更符合逻辑，这个时候就需要自底向上，对应的方法是使用后序遍历，因为后序遍历先处理左右节点，最后处理根节点。比如判断平衡二叉树，它要求从下往上，每一个子树的高度差都不超过1。
自顶向下
自顶向下可以从根节点开始，比如：
有些看着像是从下往上，但实际上还是从上往下。比如：
也不过是自root向leaf，然后反过来排个序罢了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public String smallestFromLeaf(TreeNode root) {
PriorityQueue<String> pq = new PriorityQueue<>();
dfs(pq, "", root);
return pq.size() == 0 ? "" : pq.poll();
}
private void dfs(PriorityQueue<String> result, String cur, TreeNode root) {
if (root == null) {
return;
}
// cur.append((char) (root.val + 'a'));
cur += (char)(root.val + 'a');
if (root.left == null && root.right == null) {
result.offer(new StringBuilder(cur).reverse().toString());
// 精简一下，反正只要第一个，试试速度
if (result.size() > 1) {
String first = result.poll();
result.clear();
result.offer(first);
}
} else {
dfs(result, cur, root.left);
dfs(result, cur, root.right);
}
// 不用回退，因为String是传值，不是传引用
// cur.deleteCharAt(cur.length() - 1);
}
}
自顶向下也可以不从根节点开始，关键点就是：
- 不从根节点开始：意味着多加一层递归，把每个节点都当做root来一次；
- 如果也不到叶节点结束：意味着当找到合适的路径之后，不要return（相当于不剪枝），继续递归下去；
比如：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public int pathSum(TreeNode root, int targetSum) {
if (root == null) {
return 0;
}
int ret = 0;
ret += sum(root, targetSum);
ret += pathSum(root.left, targetSum);
ret += pathSum(root.right, targetSum);
return ret;
}
// 没有像之前一样传个sum，因为直接拿target - node.value了
private int sum(TreeNode root, long targetSum) {
int ret = 0;
if (root == null) {
return 0;
}
if (root.val == targetSum) {
// result.add(new ArrayList<>(cur));
ret++;
}
// 不管是否满足条件，都要继续递归下去
ret += sum(root.left, targetSum - root.val);
ret += sum(root.right, targetSum - root.val);
return ret;
}
}
如果要所有的情况，则使用list承接，使用cur list做加、减，以回溯：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public int pathSum(TreeNode root, int targetSum) {
List<List<Integer>> result = new ArrayList<>();
dfs(result, root, targetSum);
return result.size();
}
private void dfs(List<List<Integer>> result, TreeNode root, int targetSum) {
if (root == null) {
return;
}
sum(result, new ArrayList<>(), root, 0, targetSum);
dfs(result, root.left, targetSum);
dfs(result, root.right, targetSum);
}
private void sum(List<List<Integer>> result, List<Integer> cur, TreeNode root, int sum, int target) {
if (root == null) {
return;
}
sum += root.val;
cur.add(root.val);
if (sum == target) {
result.add(new ArrayList<>(cur));
}
// 不管是否满足条件，都要继续递归下去
sum(result, cur, root.left, sum, target);
sum(result, cur, root.right, sum, target);
cur.remove(cur.size() - 1);
}
}
最后再说个例子——经常面别人的树的覆盖，这里有一个类似的题另一棵树的子树，其实也是不从根节点开始。不过这个不是树的覆盖，所以这个比较到leaf了。
在LeetCode上竟然是简单题……
自底向上：O(n)
上面已经介绍过了，逻辑上从下往上的情况应该用自底向上的算法，那就是后序遍历！比如判断平衡二叉树：
如果用自顶向下，就会比较重复，比如判断第一层的高度，要遍历整个二叉树，判断第二层的时候，要再遍历一遍。所以整个算法是O(n)*O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
return (Math.abs(depth(root.left) - depth(root.right)) <= 1) && isBalanced(root.left) && isBalanced(root.right);
}
private int depth(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + Math.max(depth(root.left), depth(root.right));
}
}
先来看一个不成功的自底向上。第一个方法是后序遍历，所以是自底向上；第二个方法依然是前序，所以是自顶向下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
// 最后判断本层，所以是自下而上判断
return isBalanced(root.left) && isBalanced(root.right) && (Math.abs(depth(root.left) - depth(root.right)) <= 1);
}
private int depth(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + Math.max(depth(root.left), depth(root.right));
}
}
这个算法中，isBalanced采用了后序遍历，先判断底层是不是平衡二叉树，最后判断本层。但是没什么卵用，因为非平衡二叉树不一定是从哪儿开始不平衡的，可能是上面也可能是下面，所以从哪儿开始判断并没有太大区别。本质上，它每次还是重新计算了每一个子树的高度。
所以真正的自底向上应该是自底向上算高度，同时判断是否符合平衡二叉树要求。这样最终只对每个值算了一次高度，而且用上了之前子节点的高度信息，一遍就搞定了，算法为O(n)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public boolean isBalanced(TreeNode root) {
return depth(root) != -1;
}
private int depth(TreeNode root) {
if (root == null) {
return 0;
}
// 先算左右，再处理root，所以是自底向上
int l = depth(root.left), r = depth(root.right);
// 为了能在计算高度的同时返回是否为平衡二叉树（true/false），选择用是否为-1来代表true/false，因此返回int就行了
if (l == -1 || r == -1 || Math.abs(l - r) > 1) {
return -1;
}
return 1 + Math.max(l, r);
}
}
自底向上模板
求树的高度，本身就是自底向上。求树的深度，应该用自顶向下。但是root节点的高度和深度是一样的，所以一般也写成自底向上。https://cloud.tencent.com/developer/article/1859061
自顶向下求树的高度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int result;
void getDepth(TreeNode* node, int depth) {
result = depth > result ? depth : result; // 中
if (node->left == NULL && node->right == NULL) return ;
if (node->left) { // 左
getDepth(node->left, depth + 1);
}
if (node->right) { // 右
getDepth(node->right, depth + 1);
}
return ;
}
int maxDepth(TreeNode* root) {
result = 0;
if (root == 0) return result;
getDepth(root, 1);
return result;
}
};
分割线————-
这种自底向上题的套路都是：
- 后序遍历；
- 按照题意找到本节点（未必是全局）的“高度”，这个高度未必是物理上的树高，而是满足题意的一种metric。因为上层节点只能用它的root连接本子树的高度；
- 方法返回的是当前节点的“高度”；
- 同时更新max：本节点使用root连接两颗子树的“高度”，得到题目中规定的max。然后找个全局max更新一下所有节点中最大的那个max即可。
如果用套路重写上面的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
// 全局的“max”
boolean balance = true;
public boolean isBalanced(TreeNode root) {
depth(root);
return balance;
}
private int depth(TreeNode root) {
if (root == null) {
return 0;
}
// 先算左右，再处理root，所以是自底向上
int l = depth(root.left), r = depth(root.right);
if (Math.abs(l - r) > 1) {
balance = false;
}
// 本节点想判断是否平衡，就是需要求本节点的高度
return 1 + Math.max(l, r);
}
}
二叉树的直径，一模一样的问题！如果是自顶向下，O(n^2)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int diameterOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}
// 过root的路径数、左子树的最大直径、右子树的最大直径
return Math.max(height(root.left) + height(root.right), Math.max(diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right)));
}
private int height(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + Math.max(height(root.left), height(root.right));
}
}
自底向上，O(n)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
int max = -1;
public int diameterOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}
height(root);
return max;
}
private int height(TreeNode root) {
if (root == null) {
return 0;
}
int l = height(root.left);
int r = height(root.right);
// 求高度的同时，记录下最大值。这次height函数不能返回两个值了，只能用全局变量了……符合上述“模板套路”
// 思想是一致的，自底向上——后序遍历
max = Math.max(max, l + r);
// 本节点的max，就是最高的左右子树之和
return 1 + Math.max(l, r);
}
}
最长同值路径，这个子树的高度就是左右子树和root同值的情况下的子树高度的最大值：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
// 路径，最小也就是0了
int max = 0;
public int longestUnivaluePath(TreeNode root) {
height(root);
return max;
}
private int height(TreeNode root) {
if (root == null) {
return 0;
}
int l = height(root.left);
int r = height(root.right);
// 算的是路径长度
int cur = 0;
if (sameValue(root.left, root)) {
cur += l;
}
if (sameValue(root.right, root)) {
cur += r;
}
max = Math.max(max, cur);
// 返回的是每个点能积累的当前路径长度
return 1 + Math.max((sameValue(root.left, root) ? l : 0), (sameValue(root.right, root) ? r : 0));
}
private boolean sameValue(TreeNode a, TreeNode b) {
if (a == null) {
return b == null;
}
if (b == null) {
return a == null;
}
return a.val == b.val;
}
}
稍微合并一下，就是我们看到的模板代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
// 路径，最小也就是0了
int max = 0;
public int longestUnivaluePath(TreeNode root) {
height(root);
return max;
}
private int height(TreeNode root) {
if (root == null) {
return 0;
}
int l = height(root.left);
int r = height(root.right);
int adjustL = sameValue(root.left, root) ? l : 0;
int adjustR = sameValue(root.right, root) ? r : 0;
// 算的是路径长度
max = Math.max(max, adjustL + adjustR);
// 返回的是每个点能积累的当前路径长度
return 1 + Math.max(adjustL, adjustR);
}
private boolean sameValue(TreeNode a, TreeNode b) {
if (a == null) {
return b == null;
}
if (b == null) {
return a == null;
}
return a.val == b.val;
}
}
二叉树中的最大路径和。这个子树的“高度”更虚幻一些，不是左右子树的物理高度，而是叠加值高度。需要注意的点是，端点不需要必须是叶子。所以这里处理的时候需要注意一下，如果子子树积累过来的值是负的，我们不加上它就行了，也就是设为0：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
sum(root);
return max;
}
private int sum(TreeNode root) {
if (root == null) {
return 0;
}
int l = sum(root.left);
int r = sum(root.right);
// 如果左右子树贡献的是负的，就不加上了
int adjustL = Math.max(l, 0);
int adjustR = Math.max(r, 0);
// 最终求的是最大路径和
max = Math.max(max, root.val + adjustL + adjustR);
// 但是dfs返回的是当前子树的最大“高度”
return root.val + Math.max(adjustL, adjustR);
}
}
只是为了遍历一遍
对于那些只是为了遍历一遍,或者对于那些要求返回的信息比较多的题，比如二叉树的堂兄弟节点，如果用dfs，返回的信息不够。这个时候如果用dfs，那么dfs就是为了遍历一遍而已，所以可以用任何序（自顶向下自底向上都无所谓的），不用返回任何信息，而是用全局变量记录x和y的深度和父节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public boolean isCousins(TreeNode root, int x, int y) {
// root没有父节点id，瞎传一个
dfs(root, x, y, 0, -2);
return depthX == depthY && parentX != parentY;
}
int depthX = -1, depthY = -1, parentX = -1, parentY = -1;
private void dfs(TreeNode root, int x, int y, int depth, int parentId) {
if (root == null) {
return;
}
if (root.val == x) {
depthX = depth;
parentX = parentId;
}
if (root.val == y) {
depthY = depth;
parentY = parentId;
}
dfs(root.left, x, y, depth + 1, root.val);
dfs(root.right, x, y, depth + 1, root.val);
}
}
再回头看一下二叉树中的最大路径和，dfs除了跑一遍，还要算子树路径和，所以是自底向上，dfs跑的时候得用后序遍历，但是它也是返回的信息不够，所以用全局变量记录。
本文由作者按照 CC BY 4.0 进行授权