河北省住房城乡建设厅网站首页,个人网站注册费用,网站开发的国内外研究现状,织梦网站301重定向二叉树的最近公共祖先 题目描述递归法代码演示 上期经典 题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为#xff1a;“对于有根树 T 的两个节点 p、q#xff0c;最近公共祖先表示为一个节点 x#xff0c;满足 x 是 p、q … 二叉树的最近公共祖先 题目描述递归法代码演示 上期经典 题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为“对于有根树 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. 计算右侧小于当前元素的个数
