Published: Sep 26, 2022
This is a popular LCA problem. The depth-first search by recursion is a common solution.
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
qas the lowest node in
Tthat has both
qas descendants (where we allow a node to be a descendant of itself).”
- The number of nodes in the tree is in the range
-10**9 <= Node.val <= 10**9
- All Node.val are unique.
p != q
qwill exist in the tree.
Example 1 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. 3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4
Example 2 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. 3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4
Example 3 Input: root = [1,2], p = 1, q = 2 Output: 1
The recursion’s base case is, whether root is None, p or q. If both left and right subtree return nodes, the current root is the LCA. If one of left or right subtree returns the node, the current root is on the path to LCA. In such a case, return the node comes from the subtree.
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class LCA: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if not root or root == p or root == q: return root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if left and right: return root return left or right