二叉树的最近公共祖先
- 题目描述
- 递归法
- 代码演示
- 上期经典
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
示例1:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。
示例2:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出:5
解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3:
输入:root = [1,2], p = 1, q = 2
输出:1
提示:
树中节点数目在范围 [2, 1e5] 内。
-109 <= Node.val <= 1e9
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。
递归法
这道题目中说, p 和 q 均存在于给定的二叉树中。 但会有不同的情况:
两个节点的最近公共祖先其实就是这两个节点向根节点的「延长线」的交汇点,那么对于任意一个节点,它怎么才能知道自己是不是p和q的最近公共祖先?
如果一个节点能够在它的左右子树中分别找到p和q,则该节点为LCA节点。
代码演示
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {return find(root, p.val, q.val);
}// 在二叉树中寻找 val1 和 val2 的最近公共祖先节点
TreeNode find(TreeNode root, int val1, int val2) {if(root == null){return null;}//在root节点=p 或者 ==q ,那么这个节点肯定就是最近祖先if(root.val == val1 || root.val == val2){return root;}TreeNode left = find(root.left,val1,val2);TreeNode right = find(root.right,val1,val2);//在root节点的左右节点找到p和q 那么root 就是最近公共祖先if(left != null && right != null){return root;}//如果root 上没找到,那么肯定是左右子节点上其中一个。return left != null ? left : right;
}
}
不过需要注意的是,这两道题的题目都明确告诉我们这些节点必定存在于二叉树中,如果没有这个前提条件,就需要修改代码了。
上期经典
LC315. 计算右侧小于当前元素的个数