aloalgoLowest Common Ancestor of a Binary Tree
Medium
You are given a binary tree and two distinct nodes, p and q.
Your task is to find the lowest common ancestor (LCA) of nodes p and q. The LCA is defined as the lowest node in the tree that has both p and q as descendants.
You may assume that:
- A node can be considered a descendant of itself.
- Both
pandqwill always exist in the given tree. - Nodes
pandqwill always be distinct from each other.
Return the LCA node.
Example 1
Inputs
p = 2
q = 3
Output
1
Explanation:
The LCA of nodes with values 2 and 3 is the node with value 1, which is their parent.
Example 2
Inputs
p = 1
q = 2
Output
1
Explanation:
The LCA of nodes with values 1 and 2 is the node with value 1, since a node can be a descendant of itself.
Example 3
Inputs
p = 8
q = 5
Output
2
Explanation:
The LCA of nodes with values 8 and 5 is the node with value 2, which is their lowest common ancestor.
Inputs
p = 2
q = 3
Output
1