NC102:在二叉树中找到两个节点的最近公共祖先

在二叉树中找到两个节点的最近公共祖先

http://www.nowcoder.com/questionTerminal/e0cc33a83afe4530bcec46eba3325116

解法1:递归
考虑两个结点的存在情况:

  1. 一个节点为是另外一个节点的子或孙子节点,此时只要判断root节点等于其中一个节点即可;
  2. 两个节点分属两支,此时两个节点都是root节点的子或孙结点,同时在root.left和root.right中各能找到一个节点;
  3. 如果不属于以上两种情况,对root.left和root.right递归判断。
   public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        return CommonAncestor(root, o1, o2).val;
    }
    public TreeNode CommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        if(root==null || root.val==o1 || root.val==o2){
            return root;
        }
        TreeNode left=CommonAncestor(root.left,o1,o2);
        TreeNode right=CommonAncestor(root.right,o1,o2);
        if(left==null){
            return right;
        }
        if(right==null){
            return left;
        }
        return root;
    }

解法2:两个结点的路径
首先找到根节点到两个节点的路径,然后将其中一个路径加入到哈希表或者链表中,然后遍历另一个路径,在哈希表\链表中有相同的则返回即可

public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        List<Integer> path1 = new ArrayList<>();
        List<Integer> path2 = new ArrayList<>();
        path1.add(root.val);
        getPath(root, o1, path1);
        path2.add(root.val);
        getPath(root, o2, path2);
        int res = 0;
        for (int i = 0; i < path1.size() && i < path2.size(); i++) {
            if (path1.get(i) == path2.get(i))
                res = path1.get(i);
            else
                break;
        }
        return res;
    }
    private boolean getPath(TreeNode root, int node, List<Integer> path) {
        if (root.val == node) 
            return true;
        if (root.left != null) {
            path.add(root.left.val);
            if (getPath(root.left, node, path)) 
                return true;
            else path.remove(path.size()-1);
        }
        if (root.right != null) {
            path.add(root.right.val);
            if (getPath(root.right, node, path)) 
                return true;
            else 
                path.remove(path.size()-1);
        }
        return false;
    }
名企高频面试算法题解 文章被收录于专栏

牛客题霸 - 程序员面试高频题 - 题解

全部评论

相关推荐

ohs的小木屋:比不少实习待遇高了
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务