- Lowest Common Ancestor of a Binary Tree
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, 10^5]
. -10^9 <= Node.val <= 10^9
- All
Node.val
are unique. p != q
p
andq
will exist in the tree.
Idea
递归思路:
* 如果当前节点为空或者与p,q任意之一相等,则说明当前节点为p,q最近公共祖先
* 否则分别再在左子树和右子树查找p,q
** 如果左子树 和 右子树 同时找到p,q,则说明当前节点为p,q公共节点
** 如果只是左子树找到,则说明找到的节点为p,q公共最近祖先
** 如果只是右子树找到,则说明找到的节点为p,q公共最近祖先
JavaScript Solution
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
if(!root || root == p || q == root ){
return root
}
let left = lowestCommonAncestor(root.left, p, q)
let right = lowestCommonAncestor(root.right, p, q)
return !left ? right : !right ? left : root
};