05 August 2008
给定二叉树的根，每个节点的深度是到根的最短距离。
返回最小的子树，使其包含原始树中所有最深的节点。
如果一个节点在整个树中的任何节点中具有最大的可能深度，则称为最深节点。
节点的子树是由该节点加上该节点所有后代的集合组成的树。
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
class Solution {
TreeNode result;
int maxDepth;
public TreeNode subtreeWithAllDeepest(TreeNode root) {
maxDepth = 1;
postOrder(root, 1);
return result;
}
public int postOrder(TreeNode root, int depth) {
if (root == null)
return depth;
int left = postOrder(root.left, depth + 1);
int right = postOrder(root.right, depth + 1);
//Due to postorder nature, we will always get lowest subtree first,
//we need to only check if the depth are same and greater/equal than max depth just update,
//because there is possibility that max depth leaves of same depth are in different subtrees.
if (left == right && left >= maxDepth) {
result = root;
maxDepth = left;
}
return Math.max(left, right);
}
}
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
41
42
43
44
45
46
47
class Solution {
public TreeNode subtreeWithAllDeepest(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
if (root == null)
return root;
queue.add(root);
HashMap<TreeNode, TreeNode> mapOfNodes = new HashMap<>();
while (!queue.isEmpty()) {
Queue<TreeNode> tempQ = new LinkedList<TreeNode>();
for (TreeNode node : queue) {
if (node.left != null) {
tempQ.add(node.left);
mapOfNodes.put(node.left, node);
}
if (node.right != null) {
tempQ.add(node.right);
mapOfNodes.put(node.right, node);
}
}
if (tempQ.size() == 0) {
break;
} else {
queue = tempQ;
}
}
return getSharedParent(queue, mapOfNodes);
}
private TreeNode getSharedParent(Queue<TreeNode> queue, HashMap<TreeNode, TreeNode> mapOfNodes) {
while (!queue.isEmpty()) {
if (queue.size() == 1) return queue.poll();
Queue<TreeNode> tempQ = new LinkedList<TreeNode>();
for (TreeNode t : queue) {
if (!tempQ.contains(mapOfNodes.get(t))) {
tempQ.add(mapOfNodes.get(t));
}
}
queue = tempQ;
}
return null;
}
}