LeetCode - Lowest Common Ancestor of a Binary Tree
Problem description
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
Example 1:
1
2
3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
1
2
3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Note:
- All of the nodes’ values will be unique.
- p and q are different and both values will exist in the binary tree.
Analysis
The basic idea is to use recursion. If we find p or q, we return it. If we find a not null node in the left and a not null node in the right. Then this node is the LCA. If we only find one not null node, then that node would be the LCA. Since we didn’t find p or q on the other subtree.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null){
return null;
}
if (root == p || root == q){
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null){
return root;
}
else if (left != null){
return left;
}
else if (right != null){
return right;
}
return null;
}