栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

剑指offer 86:在二叉树中找到两个节点的最近公共祖先

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

剑指offer 86:在二叉树中找到两个节点的最近公共祖先

剑指offer 86

详细解析:二叉树的最近公共祖先

题目:
给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 p和 q,请找到 p 和 q 的最近公共祖先节点。

思路:

自底向上搜索为后序遍历-------回溯算法思想

三种情况:

  1. 如果 p 和 q 都在以 root 为根的树中,函数返回的即使 p 和 q 的最近公共祖先节点。
  2. 那如果 p 和 q 都不在以 root 为根的树中 返回 null
  3. 很多人容易忽略的一个情况,就是节点本身p,它拥有一个子孙节点q
    假设当找到一个节点是p(目标节点)的时候,直接返回当前目标节点,无需再继续递归子树,就算后序找到节点q(子孙节点),则p和q的公共节点还是p ! 所以无需再遍历!
    如例中5是4的公共节点,遇到5直接返回5即可,无需再往下遍历到4,计算遍历到4,结果还是5。

本题递归有返回值,因为回溯的过程需要递归函数的返回值做判断

如果搜索整个树,则用变量left、right接住返回值,这个left、right后序还有逻辑处理的需要,也就是后序遍历中处理中间节点的逻辑(也是回溯)。

递归三部曲:

  1. 参数已给,返回值为root,这里用辅助函数
  2. 终止条件,root为 目标节点 p或者 q 或者null,直接返回root !
  3. 单层逻辑: 后序遍历,通过遍历的结果 left和right进行判断,
    如果都不为null即root就是公共祖先(root左右各一个目标节点)!
    如果都为null则为返回null ;
    如果一方为null,另一方不为null,即不为null的是公共祖先
Java实现:
public class Solution {
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // 自底向上,后序遍历-----回溯
        // 且用left和right记录递归的值
        return check(root,o1,o2).val;
    }
    
    private TreeNode check(TreeNode root, int o1, int o2){
    // 终止条件, 返回目标节点or null
        if(root==null || root.val==o1 || root.val==o2){
            return root;
        }
        TreeNode left=check(root.left,o1,o2);
        TreeNode right=check(root.right,o1,o2);
        
        // 利用left和right做判断
        if(left!=null && right!=null){
            return root; // 即root为公共祖先
        }
        if(left==null && right==null){
            return null;
        }
        if(left==null){
            return right;
        }else{
            return left;
        } // 即不为null的是公共祖先
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/939255.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号