05 August 2008
给定二叉树的根，返回其最深叶子的最低共同祖先。
回顾：
二叉树的节点是叶子当且仅当它没有孩子
树根的深度为 0。如果一个节点的深度为 d，则其每个子节点的深度为 d + 1。
一组节点 S 的最低共同祖先是具有最大深度的节点 A，使得 S 中的每个节点都在具有根 A 的子树中。
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
class Solution {
public class Pair {
TreeNode node;
int d;
public Pair(TreeNode node, int d) {
this.node = node;
this.d = d;
}
}
public TreeNode lcaDeepestLeaves(TreeNode root) {
Pair p = getLca(root, 0);
return p.node;
}
private Pair getLca(TreeNode node, int d) {
if (node == null) return new Pair(null, d);
Pair l = getLca(node.left, d + 1);
Pair r = getLca(node.right, d + 1);
if (l.d == r.d) return new Pair(node, l.d);
if (l.d > r.d) return l;
return r;
}
}
BFS
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 {
public TreeNode lcaDeepestLeaves(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.remove();
int leftDepth = depth(node.left);
int rightDepth = depth(node.right);
if (leftDepth == rightDepth) return node;
if (leftDepth > rightDepth && node.left != null) queue.offer(node.left);
if (rightDepth >= leftDepth && node.right != null) queue.offer(node.right);
}
return null;
}
private int depth(TreeNode node) {
if (node == null) return 0;
return Math.max(depth(node.left), depth(node.right)) + 1;
}
}