网页设计网站怎么做,济南住房和城乡建设厅网站,品牌推广策划方案,企业解决方案 msdn技术资源库二叉树寻找祖先问题-算法通关村 1 最近公共祖先问题 LeetCode236#xff1a;给定一个二叉树#xff0c;找到该树中两个指定节点的最近公共祖先。 最近公共祖先的定义为#xff1a;“对于有根树T 的两个节点 p、q#xff0c;最近公共祖先表示为一个节点 x#xff0c;满足是…二叉树寻找祖先问题-算法通关村 1 最近公共祖先问题 LeetCode236给定一个二叉树找到该树中两个指定节点的最近公共祖先。 最近公共祖先的定义为“对于有根树T 的两个节点 p、q最近公共祖先表示为一个节点 x满足×是p、q的祖先且 × 的深度尽可能大一个节点也可以是它自己的祖先。” 例如对于下面的二叉树 示例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 和 节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。 要想找到两个节点的最近公共祖先节点我们可以**从两个节点往上找每个节点都往上走一直走到根节点那么根节点到这两个节点的连线肯定有相交的地方如果是从上往下走那么最后一次相交的节点就是他们的最近公共祖先节点。**我们就以找6和7的最近公共节点来画个图看一下 6 的祖先结点有3 和57的是352所以6和7的最近公共祖先是5。如果要用代码实现需要考虑好几种情况。根据以上定义若 root是 p,q的 最近公共祖先则只可能为以下情況之一 1p和 q 在 root 的子树中且分列 root 的 异侧即分别在左、右子树中 2proot且q在 root 的左或右子树中 3q root且p在 root 的左或右子树中 而具体在执行递归时我们要判断的情况稍微复杂一些例如我们在上面的树中查找6和7的公共祖先遍历的时候从树的根节点开始逐步向下假如某个时刻访问的结点为root我们通过后序递归的查找其左右子树则此时的判断逻辑是 1.如果left和right都为null说明在该子树root里p和q一个都没找到直接返回null即可。例如上图中递归到了root为 1 的子树时。2.如果left和right都不为null说明p和q分别在root的两侧例如root为5时此时6和7就分别在其两侧直接返回5即可。3.当right为空left不为空时此时情况略复杂要考虑两种情况1先判断一下root是不是 P或者q如果是说明q和p一个是另一个的祖先直接返回就好了否则2说明right子树里什么都没查到而6和7是在left子树里此时需要递归的去左子树查即可。例如root为3时此时递归的结果必然是right为null而left不为空。4.如果left为空而right不为空说明是与情况3相反的情况。 总结看递归的代码 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){if(root null || root p || root q){return root;}TreeNode left lowestCommonAncestor(root.left, p, q);TreeNode right lowestCommonAncestor(root.right, p, q);if(left null right null){return null;}if(left null){return right;}if(right null){return left;}//left和right都不为空// 说明p和q分别位于当前节点的左右子树中// 因此当前的root就是它们的最近公共祖先。return root;}
