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).”
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.
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.
Example 3:
Input: root = [1,2], p = 1, q = 2
Output: 1
Constraints:
The number of nodes in the tree is in the range [2, 105].
-109 <= Node.val <= 109
All Node.val are unique.
p != q
p and q will exist in the tree.
Solutions
Solution 1: Recursion
We recursively traverse the binary tree:
If the current node is null or equals to $p$ or $q$, then we return the current node;
Otherwise, we recursively traverse the left and right subtrees, and record the returned results as $left$ and $right$. If both $left$ and $right$ are not null, it means that $p$ and $q$ are in the left and right subtrees respectively, so the current node is the nearest common ancestor; If only one of $left$ and $right$ is not null, we return the one that is not null.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 91011121314151617
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution:deflowestCommonAncestor(self,root:"TreeNode",p:"TreeNode",q:"TreeNode")->"TreeNode":ifrootin(None,p,q):returnrootleft=self.lowestCommonAncestor(root.left,p,q)right=self.lowestCommonAncestor(root.right,p,q)returnrootifleftandrightelse(leftorright)
1 2 3 4 5 6 7 8 910111213141516171819202122
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */classSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){if(root==null||root==p||root==q){returnroot;}varleft=lowestCommonAncestor(root.left,p,q);varright=lowestCommonAncestor(root.right,p,q);if(left!=null&&right!=null){returnroot;}returnleft==null?right:left;}}
1 2 3 4 5 6 7 8 91011121314151617181920212223
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */classSolution{public:TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){if(root==nullptr||root==p||root==q){returnroot;}autoleft=lowestCommonAncestor(root->left,p,q);autoright=lowestCommonAncestor(root->right,p,q);if(left&&right){returnroot;}returnleft?left:right;}};
1 2 3 4 5 6 7 8 910111213141516171819202122
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funclowestCommonAncestor(root,p,q*TreeNode)*TreeNode{ifroot==nil||root==p||root==q{returnroot}left:=lowestCommonAncestor(root.Left,p,q)right:=lowestCommonAncestor(root.Right,p,q)ifleft!=nil&&right!=nil{returnroot}ifleft!=nil{returnleft}returnright}