搜索

二叉树两个节点的最近公共祖先问题


发布时间: 2022-11-24 17:48:03    浏览次数:17 次

二叉树两个节点的最近公共祖先问题

作者:Grey

原文地址:

博客园:二叉树两个节点的最近公共祖先问题

CSDN:二叉树两个节点的最近公共祖先问题

题目描述

给定一棵二叉树的头节点 head,和另外两个节点 a 和 b , 返回 a 和 b 的最低公共祖先。

题目链接见:LeetCode 236. Lowest Common Ancestor of a Binary Tree

主要思路:

本题也是利用二叉树的递归套路来解。

定义好 Info 信息

    public static class Info {
        public Info(boolean findA, boolean findB, TreeNode ancestor) {
            this.findA = findA;
            this.findB = findB;
            this.ancestor = ancestor;
        }
        private boolean findA;
        private boolean findB;
        private TreeNode ancestor;

    }

其中

findA表示能否在当前(子)树下找到 a 节点;

findB表示能否在当前(子)树下找到 b 节点;

ancestor表示当前两个节点的最低公共祖先是什么。

首先考虑一些边界条件,例如

if (a == null) {
    // a 为 null,不管 b 是否为 null,公共祖先都是 b
    return b;
}
if (b == null) {
    // b 为 null, 不管 a 是否为 null,公共祖先都是 a
    return a;
}

定义递归函数

Info p(TreeNode head, TreeNode a, TreeNode b)

递归含义是:以 head 为头的树,a 和 b 的公共祖先是什么,封装成 Info 返回。

接下来看递归函数的主要逻辑

首先是 base case,如果 head 为 null,则 findA = false,findB = false,a 和 b 的公共祖先也是 null

        if (head == null) {
            return new Info(false, false, null);
        }

分析了 base case,接下来是普遍情况,如果 head 不为 null,则去左树收集信息,去右树也收集信息,然后把左右两树的信息整合成 head 的信息返回

// 左树收集信息
Info leftInfo = p(head.left, a, b);
// 右树收集信息
Info rightInfo = p(head.right, a, b);

// 整合
......

最后,我们需要把左右两树返回的信息进行整合,首先,以 head 为头的树,findA的取值取决于如下三种情况:

情况1,左树包含 a,即 leftInfo.findA

情况2,右树包含 a,即 rightInfo.findA

情况3,head 就是 a

三个情况有一个满足,以 head 为头的树 findA = true,

findB类似,

即下述代码所表达的含义

//  这
boolean findA = leftInfo.findA || rightInfo.findA || head == a;
boolean findB = leftInfo.findB || rightInfo.findB || head == b;

接下来看两个节点的最低公共祖先,首先,如果左树上找到 a 和 b,那么 leftInfo.ancestor 就是 a 和 b 的最低公共祖先;

如果右树上找到 a 和 b,那么 rightInfo.ancestor 就是 a 和 b 的最低公共祖先;

如果左右树一边找到一个,则 head 就是 a 和 b 的最低公共祖先;

如果 a 和 b 在树上都找不到,即findA = false, findB = false,那么 a 和 b 的最低公共祖先就是 null。

即下述代码逻辑

        
        if (findA && findB) {
            if (leftInfo.findA && leftInfo.findB) {
                return new Info(true, true, leftInfo.ancestor);
            } else if (rightInfo.findA && rightInfo.findB) {
                return new Info(true, true, rightInfo.ancestor);
            }
            return new Info(true, true, head);
        }
        return new Info(findA, findB, null);

完整代码见

class Solution {
    public static TreeNode lowestCommonAncestor(TreeNode head, TreeNode a, TreeNode b) {
        if (a == null) {
            return b;
        }
        if (b == null) {
            return a;
        }
        // o1和o2都不为null
        return p(head, a, b).ancestor;
    }

    public static Info p(TreeNode head, TreeNode a, TreeNode b) {
        if (head == null) {
            return new Info(false, false, null);
        }
        Info leftInfo = p(head.left, a, b);
        Info rightInfo = p(head.right, a, b);
        boolean findA = leftInfo.findA || rightInfo.findA || head == a;
        boolean findB = leftInfo.findB || rightInfo.findB || head == b;
        if (findA && findB) {
            if (leftInfo.findA && leftInfo.findB) {
                return new Info(true, true, leftInfo.ancestor);
            } else if (rightInfo.findA && rightInfo.findB) {
                return new Info(true, true, rightInfo.ancestor);
            }
            return new Info(true, true, head);
        }
        return new Info(findA, findB, null);
    }

    public static class Info {
        public Info(boolean findA, boolean findB, TreeNode ancestor) {
            this.findA = findA;
            this.findB = findB;
            this.ancestor = ancestor;
        }

        private boolean findA;
        private boolean findB;
        private TreeNode ancestor;

    }
}

时间复杂度为O(N)(即一次后序遍历的时间复杂度)

更多

算法和数据结构笔记

免责声明 二叉树两个节点的最近公共祖先问题,资源类别:文本, 浏览次数:17 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-24 05:48:03。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/greyzeng/p/16757504.html