Lowest Common Ancestor
236 LCA - given 2 nodes and root in Binary tree
Time O(n), space O(h)
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) { // 碰到node1 or node2 就返回 if(root == null || root == node1 || root == node2){ return root; } TreeNode left = lowestCommonAncestor(root.left, node1, node2); TreeNode right = lowestCommonAncestor(root.right, node1, node2); if( left != null && right != null){ return root; } if(left != null){ return left; } if(right != null){ return right; } return null; }
LCA - given 2 nodes with parent pointer in same binary tree
Get depths of each nodes, make deeper node to the same level of another
Time O(h), Space O(1)
public static BinaryTree<Integer> LCA(TreeNode node0, TreeNode node1) {
int depth_0 = depthGetter(node0), depth_1 = depthGetter(node1);
// adjust node0 to make it deeper than node1
if(depth_1 > depth_0){
BinaryTree<Integer> tmp = node0;
node0 = node1;
node1 = tmp;
}
int diff = Math.abs(depth_0 - depth_1);
while( diff-- > 0){
node0 = node0.parent;
}
while(node0 != node1){
node0 = node0.parent;
node1 = node1.parent;
}
return node0;
}
LCA - given 2 nodes with parent pointer, optimize for close ancestor
Use Hashtable
Time and Space O(D0 + D1)
public static BinaryTree<Integer> LCA(TreeNode node0, TreeNode node1) {
Set<BinaryTree<Integer>> s = new HashSet<>();
while(node0 != null || node1 != null){
if(node0 != null){
if (!s.add(node0)){
return node0;
}
node0 = node0.parent;
}
if(node1 != null){
if (!s.add(node1)){
return node1;
}
node1 = node1.parent;
}
}
return null;
}
235 LCA with BST
Worst case O(h)
Keep search the root in range [node0, node1]
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(p.val > q.val){ TreeNode tmp = p; p = q; q = tmp; } while(root.val < p.val || root.val > q.val){ while(root.val < p.val) root = root.right; while(root.val > q.val) root = root.left; } return root; }
1123. Lowest Common Ancestor of Deepest Leaves
Given a rooted binary tree, return the lowest common ancestor of its deepest leaves.
class Solution:
def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
def helper(node):
if not node:
return 0, None
d1, t1 = helper(node.left)
d2, t2 = helper(node.right)
if d1 > d2: return d1+1, t1
elif d1 < d2: return d2+1, t2
else: return d1+1, node
return helper(root)[1]
Last updated
Was this helpful?