BFS
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
| class Solution {
public TreeNode subtreeWithAllDeepest(TreeNode root) {
Map<TreeNode, TreeNode> childToParentMap = new IdentityHashMap<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
Deque<TreeNode> lastLevelNodeQueue = new LinkedList<>();
while (!queue.isEmpty()) {
Deque<TreeNode> nodeList = new LinkedList<>();
for (int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
nodeList.add(node);
if (node.left != null) {
childToParentMap.put(node.left, node);
queue.offer(node.left);
}
if (node.right != null) {
childToParentMap.put(node.right, node);
queue.offer(node.right);
}
}
lastLevelNodeQueue = nodeList;
}
while (lastLevelNodeQueue.size() > 1) {
for (int i = lastLevelNodeQueue.size(); i > 0; i--) {
TreeNode child = lastLevelNodeQueue.poll();
TreeNode parent = childToParentMap.get(child);
if (parent != lastLevelNodeQueue.getLast()) {
lastLevelNodeQueue.offer(parent);
}
}
}
return lastLevelNodeQueue.poll();
}
}
|
DFS
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 subtreeWithAllDeepest(TreeNode root) {
Map<TreeNode, Integer> depthCache = new IdentityHashMap<>();
int leftMaxDepth = maxDepth(depthCache, root.left);
int rightMaxDepth = maxDepth(depthCache, root.right);
if (leftMaxDepth < rightMaxDepth) {
return subtreeWithAllDeepest(root.right);
} else if (leftMaxDepth > rightMaxDepth) {
return subtreeWithAllDeepest(root.left);
} else {
return root;
}
}
private int maxDepth(Map<TreeNode, Integer> depthCache, TreeNode root) {
if (root == null) {
return 0;
}
Integer cachedDepth = depthCache.get(root);
if (cachedDepth != null) {
return cachedDepth;
}
int maxDepth = 1 + Math.max(maxDepth(depthCache, root.left), maxDepth(depthCache, root.right));
depthCache.put(root, maxDepth);
return maxDepth;
}
}
|
DFS
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
| class Solution {
private static class Pair {
private final TreeNode node;
private final int depth;
public Pair(TreeNode node, int depth) {
this.node = node;
this.depth = depth;
}
}
public TreeNode subtreeWithAllDeepest(TreeNode root) {
return dfs(root, 0).node;
}
private Pair dfs(TreeNode node, int depth) {
if (node == null) {
return new Pair(null, depth);
}
Pair left = dfs(node.left, depth + 1);
Pair right = dfs(node.right, depth + 1);
if (left.depth > right.depth) {
return left;
} else if (left.depth < right.depth) {
return right;
} else {
return new Pair(node, left.depth);
}
}
}
|
DFS
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
| class Solution {
private static class State {
private int maxDepth = Integer.MIN_VALUE;
private TreeNode result;
}
public TreeNode subtreeWithAllDeepest(TreeNode root) {
State state = new State();
maxDepth(state, root, 0);
return state.result;
}
private int maxDepth(State state, TreeNode root, int depth) {
if (root == null) {
return depth;
}
int leftMaxDepth = maxDepth(state, root.left, depth + 1);
int rightMaxDepth = maxDepth(state, root.right, depth + 1);
int maxDepth = Math.max(leftMaxDepth, rightMaxDepth);
if (maxDepth > state.maxDepth) {
state.maxDepth = maxDepth;
}
if (leftMaxDepth == state.maxDepth && rightMaxDepth == state.maxDepth) {
state.result = root;
}
return maxDepth;
}
}
|
此解法需要复习。
References
865. Smallest Subtree with all the Deepest Nodes
1123. Lowest Common Ancestor of Deepest Leaves