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
| class Solution {
private int count;
private int deepest;
private int found;
public TreeNode subtreeWithAllDeepest(TreeNode root) {
if (root == null) {
return null;
}
helper(root, 0);
return findSubTree(root, 0);
}
private void helper(TreeNode node, int depth) {
if (node == null) {
return;
}
if (depth > deepest) {
deepest = depth;
count = 1;
} else if (depth == deepest) {
count += 1;
}
helper(node.left, depth + 1);
helper(node.right, depth + 1);
}
private TreeNode findSubTree(TreeNode node, int depth) {
if (node == null) {
return null;
}
int foundNodes = found;
if (depth == deepest) {
found += 1;
if (found - foundNodes == count) {
return node;
} else {
return null;
}
}
TreeNode leftTree = findSubTree(node.left, depth + 1);
if (leftTree != null) {
return leftTree;
}
if (found - foundNodes == count) {
return node;
}
TreeNode rightTree = findSubTree(node.right, depth + 1);
if (rightTree != null) {
return rightTree;
}
if (found - foundNodes == count) {
return node;
}
return null;
}
}
|
这是我自己写的第一版. 首先是看deepest nodes的count是多少. 然后看哪个树包含了所有的. 由于是递归, 因此从下到上第一个遇到的包含所有的deepest nodes的node就是答案. 递归函数等于是在dfs, 然后到一个node的时候看找到了多少个deepest nodes, 回来的时候又找到了多少个. 只有是刚来的时候一个没找到, 回来的时候发现全找到了. 这就是LCA的特征.
其实仔细想一想, 所有deepest nodes的LCA, 如果只有一个deepest node, 那么它自己就是LCA; 如果有多个, 那么任何一个deepest node都不可能是LCA. 有了这个判断, 其实我们之前写的答案里面有些就是冗余的. 比如33行的判断, 这一行只有在一个地方会激活那就是如果只有一个deepest node的时候. 其实我们可以先找左支, 再找右支, 最后再看自己是不是deepest. 最后再判断自己代表的树是否包含了所有的deepest. 这样的话即使是只有一个deepest的情况, 先看左再看右会遇到null直接返回回来, 也不怎么耗费东西. 而且需要注意的是我们在遍历完左树后, 只需要判断左树是否找到了LCA, 不需要判断此时自己是不是就是LCA. 因为如果一个node是LCA, 那它左右两支树一定都包含有deepest nodes(除了只有一个deepest node的情况). 为什么? 我们想像所有的deepest nodes都往上走, 最终会交汇到一个点, 这个点就是LCA. 假设这个点没有一边的支, 那么等于说是所有的deepest nodes 全都是从一条路来到了这个node. 那这样的话, 该node唯一的child岂不是比该node更靠下, 而且也包含了所有的deeepst nodes? 因此我们的假设不成立.
当我们把左右两树都找完后, 再判断自己是否是deepest, 然后只有这样, 再判断自己是否为LCA.
因此可以写成下面这个样子:
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
| class Solution {
private int count;
private int deepest;
private int found;
public TreeNode subtreeWithAllDeepest(TreeNode root) {
if (root == null) {
return null;
}
helper(root, 0);
return findSubTree(root, 0);
}
private void helper(TreeNode node, int depth) {
if (node == null) {
return;
}
if (depth > deepest) {
deepest = depth;
count = 1;
} else if (depth == deepest) {
count += 1;
}
helper(node.left, depth + 1);
helper(node.right, depth + 1);
}
private TreeNode findSubTree(TreeNode node, int depth) {
if (node == null) {
return null;
}
int foundNodes = found;
TreeNode leftTree = findSubTree(node.left, depth + 1);
if (leftTree != null) {
return leftTree;
}
TreeNode rightTree = findSubTree(node.right, depth + 1);
if (rightTree != null) {
return rightTree;
}
if (depth == deepest) {
found += 1;
}
return found - foundNodes == count ? node : null;
}
}
|
这样看起来就漂亮多了.
时间复杂度: O(n)
空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public TreeNode subtreeWithAllDeepest(TreeNode root) {
return helper(root).getValue();
}
private Pair<Integer, TreeNode> helper(TreeNode node) {
if (node == null) {
return new Pair(0, null);
}
Pair<Integer, TreeNode> left = helper(node.left);
Pair<Integer, TreeNode> right = helper(node.right);
int leftDepth = left.getKey();
int rightDepth = right.getKey();
return new Pair(Math.max(leftDepth, rightDepth) + 1,
leftDepth == rightDepth ? node : leftDepth > rightDepth ? left.getValue() : right.getValue());
}
}
|
Lee哥的神解法. 之前讨论的是如果是所有deepest nodes的LCA, 那么它们的左右肯定都有deepest nodes. 换句话说, 它们的左右树的height肯定是一样的. 当然也有可能不是LCA的node同样满足这个条件, 那如何区分它们的? 那就是看最大的height. 我们先看自己的左右支的height是否相同, 如果相同, 我们就返回自己, 如果不相同, 那就返回最大的那个, 因为这个很有可能就是答案.
按照上面的逻辑, 我们最终得到的就是那个左右支height相同的node并且它所包含的node是最深的.
时间复杂度: O(n)
空间复杂度: 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
| class Solution {
private int deepest = 0;
private TreeNode ans = null;
public TreeNode subtreeWithAllDeepest(TreeNode root) {
dfs(root, 0);
return ans;
}
private int dfs(TreeNode node, int level) {
if (node == null) {
deepest = Math.max(deepest, level);
return level;
}
int leftDeepest = dfs(node.left, level + 1);
int rightDeepest = dfs(node.right, level + 1);
int currDeepest = Math.max(leftDeepest, rightDeepest);
if (leftDeepest == deepest && rightDeepest == deepest) {
ans = node;
}
return currDeepest;
}
}
|
这个最好理解. 递归函数的功能就是我们传进去一个tree, 它告诉我们这个tree包含的nodes中, 最深的node的depth是多少. 根据我们之前的证明, 所有deepest nodes的左树和右树都应该包含deepest nodes(当然如果只有一个deepest nodes除外). 因此我们可以把null假设也为nodes, 这样的话, 即使只有一个deepest non-null node, 它也满足左右树都包含deepest nodes, 尽管这两个nodes都是null. 于是我们用一个global variable记录deepest是多少. 我们知道deepest只能在null处达到. 因此在遇到null的时候更新deepest即可.
时间复杂度: O(n)
空间复杂度: O(n)
