LCA (Lowest Common Ancestor) 中文名称"最近公共祖先"。是指在树中,两个节点的最近的公共根。LeetCode里面的236题讲的就是这个。
实现
方法1:recursion
public TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == null || q == null) {
return null;
}
if (root == p || root == q) { // 因为root是从上往下的,所以这里对应的情况像是p完全在q的上面,或者q完全在p的上面
return root;
}
TreeNode left = lca(root.left, p, q);
TreeNode right = lca(root.right, p, q);
if (left == null) { // 左边没有lca
return right;
}
if (right == null) { // 右边没有lca
return left;
}
return root; // 左右都有找到match,说明pq一个match了左,一个match了右,那lca其实是root
}
方法2:iteration
public TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
Map<TreeNode, TreeNode> parents = new HashMap<>();
Deque<TreeNode> stack = new ArrayDeque<>();
parents.put(root, null);
stack.push(root);
while (!parents.containsKey(p) || !parents.containsKey(q)) { // 把pq的上面的路径都记录了下来
TreeNode node = stack.pop();
if (node.left != null) {
parents.put(node.left, node);
stack.push(node.left);
}
if (node.right != null) {
parents.put(node.right, node);
stack.push(node.right);
}
}
Set<TreeNode> ancestors = new HashSet<>();
while (p != null) {
ancestors.add(p); // 把p的所有parent都记录下来
p = parents.get(p); // 把p变成它的parent
}
while (!ancestors.contains(q)) { // 还没有遇到一样的parent
q = parents.get(q);
}
return q;
}
时间复杂度都是O(n)
空间复杂度都是O(h),最情况是O(n)
相关题目
124 Binary Tree Maximum Path Sum
https://leetcode.com/problems/binary-tree-maximum-path-sum/
235 Lowest Common Ancestor of a Binary Search Tree
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
236 Lowest Common Ancestor of a Binary Tree
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
网友评论