当前位置:首页 > 技术 > 正文内容

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

Lotus2022-10-06 18:15技术

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

作者: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)(即一次后序遍历的时间复杂度)

更多

算法和数据结构笔记

扫描二维码推送至手机访问。

版权声明:本文来源于网络,仅供学习,如侵权请联系站长删除。

本文链接:https://news.layui.org.cn/post/109.html

分享给朋友:

“二叉树两个节点的最近公共祖先问题” 的相关文章

【存储数据恢复】某品牌EqualLogic系列存储介绍&常见故障的数据恢复方法

某品牌EqualLogic系列存储介绍: 某品牌EqualLogic系列存储可以通过连接串口先对存储进行初始化。 通过浏览器登录配置的ip地址,账号默认:grpadmin,密码默认:grpadmin;也可以通过串口登陆查看状态。 卷的划分和访问如下图: 底层结构: 以9块盘组建磁盘阵列为例,该存储在创建RAID的时候,会默认分配一块热备盘,并不是全局热备。 用8块...

【微信小程序】认识小程序页面

????系列专栏:微信小程序 ????欢迎关注????点赞????收藏⭐留言???? ✅个人主页:​​hacker_demo的51CTO博客​​ ????个人格言:不断的翻越一座又一座的高山,那样的人生才是我想要的。这一马平川,一眼见底的活,我不想要,我的人生,我自己书写,余生很长,请多关照,我的人生,敬请期待???????????? 新建小程序页面 只需要在app.json->...

十年技术进阶路,让我明白了三件要事(8000字长文)

前言   【本文于2022-5-10日首发于ITPUB微信公众号平台】   该篇文章是我第一次跟DTCC合作编写的,整篇文章大概8000字,可能花您15分钟阅读。我和DTCC的韩楠老师,共花7了天时间,每天把该文章打磨到晚上12点,在这非常感谢编辑老师的负责与付出。   这篇也是我分享里为数不多“进阶”与“成长经历”的文章之一。被别人送到嘴边的食物永远是最香的,但是咱们还是得学会主动去"如何找吃的...

【大话云原生】微服务篇-五星级酒店的服务方式

文章开始之前,我给大家推荐一个人工智能学习网站,首先说我之前是完全不涉及人工智能领域的,但是我尽然看懂了,以后老哥我就要参与人工智能了。如果你也想学习,点击跳转到网站 《大话云原生》系列文章期望用最通俗、简单的语言说明云原生生态系统内的组成及应用关系。此专栏的前两篇文章 《【大话云原生】煮饺子与docker、kubernetes之间的关系》 《【大话云原生】负载均衡篇-小饭馆的流量变大了》 欢迎...

[CG从零开始] 6. 加载一个柴犬模型学习UV贴图

在第 5 篇文章中,我们成功加载了 fbx 模型,并且做了 MVP 变换,将立方体按照透视投影渲染了出来。但是当时只是随机给顶点颜色,并且默认 fbx 文件里只有一个 mesh,这次我们来加载一个柴犬模型,并且给模型贴图,模型可以从 sketchfab 下载。 本文没有涉及到理论解释,更多的是代码实践。 完整代码在 https://github.com/MangoWAY/CGLearner/tr...

java Spring创建Bean的生命周期详析

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于Spring创建Bean的生命周期的相关问题,下面一起来看一下,希望对大家有帮助。 程序员必备接口测试调试工具:立即使用 Apipost = Postman + Swagger + Mock + Jmeter Api设计、调试、文档、自动化测试工具 后端、前端、测试,同时在线协作,内容实时同步 推荐学习:《...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。