Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >二叉树oj题解析

二叉树oj题解析

作者头像
如烟花般绚烂却又稍纵即逝
发布于 2024-11-26 00:43:29
发布于 2024-11-26 00:43:29
11400
代码可运行
举报
文章被收录于专栏:javajava
运行总次数:0
代码可运行

二叉树的最近公共祖先

什么是最近公共祖先?

最近的公共祖先指的是这一棵树中两个节点中深度最大的且公共的祖先节点就是最近祖先节点。 也就是说这两个节点在树中距离最近的相交 例如:8 与6中的最近公共节点为2,因为他的最大深度就是2(在同一颗子树中)。 8与4的最近公共节点为3,因为他的最大深度是3(在左右两棵子树中的情况)。

leetcode中求二叉树中最近公共祖先

解题1.

公共祖先的三种形式: 1.题中可知:如果root根节点为q或者p,root这个节点就是最近的公共祖先节点。 2.如果p和q各自在原根节点的左右两棵子树中,则原根节点就是p和q的最近公共祖先。 3.如果p和q在根节点的同一颗子树中,则p和q的相遇之后两个节点最大深度且相交平行的第一个节点,就是最近公共祖先

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)return null;
        //q或者p如果在其中的根节点上直接返回
       if(root==p||root==q)return root;
       //向左开始递归每一棵左右树
     TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
    TreeNode rightTree= lowestCommonAncestor(root.right,p,q);
       //说明两棵树都不为null
       if(leftTree!=null&&rightTree!=null){
        return root;
       }else if(leftTree!=null){
        return leftTree;
       }else{
        return rightTree;
       }
    }
}
解题2.

前面我们也说过p和p两个节点的最大深度就是它两个的最近公共祖先,也就是相交的节点,这里的B就是它们两个的公共祖先。 那我们为什么不能将两个节点的以相同的距离开始走,最后两个节点的值相同就是最近公共祖先

假如两个节点到最近公共祖先的距离相同。 我们可以创建两个栈分别来存储到达p和q距离的所有节点,假设距离相同后pop出栈,如果出栈过程中两个节点的值相同就是它两个的公共祖先了。

这里我们如果遇到了多余的子树节点就返回false,并将其出栈,然后继续找p或者q节点找到后直接返回true。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)return null;
        Stack<TreeNode> stackP=new Stack<>();
        Stack<TreeNode> stackQ=new Stack<>();
        getTNodeLocation(root,stackP,p);
        getTNodeLocation(root,stackQ,q);
        //获取两个栈点的大小
        int sizeP=stackP.size();
        int sizeQ=stackQ.size();
        if(sizeP>sizeQ){
            int size = sizeP-sizeQ;
            while(size!=0){
                stackP.pop();
                size--;
            }
        }else{
            int size = sizeQ-sizeP;
           while(size!=0){
             stackQ.pop();
            size--;
           }
        }
        //找到两者的最近公共祖先
        while(!stackQ.isEmpty()&&!stackP.isEmpty()){
            if(stackQ.peek()==stackP.peek()){
                return stackQ.peek();
            }else{
                stackQ.pop();
                stackP.pop();
            }
        }
        return null;
    }
    //将指定的节点放入到栈中
    private boolean getTNodeLocation(TreeNode root,Stack stack,TreeNode t){
        //如果为null,返回给上一个节点false
        if(root==null)return false;
        stack.push(root);//走一步放入栈一个节点
        if(root==t)return true;//这里root如果为t直接返回
       boolean judg1 =  getTNodeLocation(root.left,stack,t);
       if(judg1==true)return true;
       boolean judg2 =  getTNodeLocation(root.right,stack,t);
       if(judg2==true)return true;
       stack.pop();//这里将出多余的节点出栈
       return false;
    }

根据二叉树创建字符串

这里的题意:对二叉树根节点进行前序的遍历,将遍历到的子树通过括号括起来,如果左子树有节点但是右子树没有节点,则将多余的右子树的括号省略,当右子树有节点但是左子树没有节点时,将左子树节点的括号添加进去。 这里的条件是:1.左子树如果为空,右子树不为空时,左右子树都有括号。 2.左子树不为空时,右子树为空,则可以忽略右树括号。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
   public String tree2str(TreeNode root) {
        StringBuilder sb=new StringBuilder();
        tree2strChild(root,sb);
        return sb.toString();
    }
    public void tree2strChild(TreeNode root,StringBuilder sb){
        if(root==null)return;
        sb.append(root.val);
        if(root.left!=null){
        sb.append("(");
        tree2strChild(root.left,sb);
        sb.append(")");
        }else{
            if(root.right!=null){
                sb.append("()");
            }
        }
        if(root.right!=null){
            sb.append("(");
            tree2strChild(root.right,sb);
            sb.append(")");
        }
    }

我的博客即将同步至腾讯云开发者社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=121ff85d13ss0

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-11-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
二叉树基础及实现(二,加经典OJ)
一 .接引二叉树(一):承接上篇,不清楚的可以回去看看:二叉树基础及实现(一)-CSDN博客 1. 判断一棵树是不是完全二叉树: 图解: 把二叉树元素放入队列中,如果最后队列里全部是元素,“null”,则该二叉树就是完全二叉树。 这里注意区分,空和元素,“null”的概念
用户11305962
2024/10/09
960
二叉树基础及实现(二,加经典OJ)
【LeetCode100】--- 二叉树的最近公共祖先
用户11288958
2025/01/21
1120
【LeetCode100】--- 二叉树的最近公共祖先
《Java初阶数据结构》----5.<二叉树的概念及使用>
树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树。它是根朝上,而叶朝下的。
用户11288958
2024/09/24
1440
《Java初阶数据结构》----5.<二叉树的概念及使用>
【java-数据结构】别再死磕理论!这些 Java 二叉树题目带你快速上手
学无止尽5
2025/03/01
911
【java-数据结构】别再死磕理论!这些 Java 二叉树题目带你快速上手
LeetCode 二叉树系统题解
TIPS:前中后序遍历区别在于三字中的中间那个字,前、中、后序分别对应左、根、右。
Yano_nankai
2019/11/10
9940
LeetCode 二叉树系统题解
Js算法与数据结构拾萃(4):二叉树
因此只要答对这道题,你就可以超越世界级大牛,问鼎码林之巅(逃) 导读: •二叉树知识重点•二叉树深度不一,因此天生适用递归,因此可用递归处理•判断两树相等•翻转二叉树•二叉树三种深度遍历(迭代)•前序遍历•中序遍历•后序遍历•二叉树的一些迭代特性•判断是否二叉搜索树•二叉搜索树的最近公共祖先•二叉树的最近公共祖先
一粒小麦
2020/02/25
6720
【Java数据结构】二叉树详解(四)
E绵绵
2025/05/24
1000
【Java数据结构】二叉树详解(四)
每日三题-翻转二叉树、二叉树的最近公共祖先、二叉树的序列化与反序列化
👨‍💻个人主页: 才疏学浅的木子 🙇‍♂️ 本人也在学习阶段如若发现问题,请告知非常感谢 🙇‍♂️ 📒 本文来自专栏: 算法 🌈 算法类型:Hot100题 🌈 ❤️ 支持我:👍点赞 🌹收藏 🤟关注 每日三题 翻转二叉树 二叉树的最近公共祖先 二叉树的序列化与反序列化 补上11月11日的每日三题 翻转二叉树 解法一 递归 class Solution { public TreeNode invertTree(TreeNode root) { if(root
才疏学浅的木子
2022/11/18
1810
每日三题-翻转二叉树、二叉树的最近公共祖先、二叉树的序列化与反序列化
LeetCode-236-二叉树的最近公共祖先
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
benym
2022/07/14
2650
LeetCode通关:连刷三十九道二叉树,刷疯了!
大家好,我是拿输出博客来督促自己刷题的老三,这一节我们来刷二叉树,二叉树相关题目在面试里非常高频,而且在力扣里数量很多,足足有几百道,不要慌,我们一步步来。我的文章很长,你们 收藏一下。
三分恶
2021/09/08
8750
【算法题解】 Day9 二叉搜索树
我们可以从题目中知道何为有效的二叉搜索树,父节点的值要大于左孩子且小于右孩子,同时所有左子树和右子树自身必须也是二叉搜索树。
sidiot
2023/08/31
1640
【算法题解】 Day9 二叉搜索树
二叉树的最近公共祖先
这道题目的看代码比较简单,而且好像也挺好理解的,但是如果把每一个细节理解到位,还是不容易的。
代码随想录
2021/09/08
2.7K0
二叉树的最近公共祖先
golang刷leetcode 技巧(12) 二叉树的最近公共祖先
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
golangLeetcode
2022/08/02
1750
求二叉树的最近公共祖先,倘若不是二叉树呢?
如果给定以下搜索二叉树: {7,1,12,0,4,11,14,#,#,3,5},如下图:
秦怀杂货店
2022/02/17
4940
求二叉树的最近公共祖先,倘若不是二叉树呢?
LeetCode——根据二叉树创建字符串与二叉树的最近公共祖先
给你二叉树的根节点 root ,请你采用前序遍历的方式,将二叉树转化为一个由括号和整数组成的字符串,返回构造出的字符串。
有礼貌的灰绅士
2023/04/17
1970
LeetCode——根据二叉树创建字符串与二叉树的最近公共祖先
《剑指 Offer(第 2 版)》树部分JavaScript题解
《剑指 Offer(第 2 版)》通行全球的程序员经典面试秘籍。剖析典型的编程面试题,系统整理基础知识、代码质量、解题思路、优化效率和综合能力这 5 个面试要点。
用户8921923
2022/10/24
4320
《剑指 Offer(第 2 版)》树部分JavaScript题解
二叉树篇二刷总结
二叉树篇,我们总共做了有关二叉树的遍历方式、求解二叉树的属性、对二叉树的修改以及构造等这几类的题型, 总结下来就是对二叉树的各种遍历方式的不同程度应用。
用户11097514
2024/05/31
1170
二叉树篇二刷总结
【力扣/牛客刷题】二叉树篇
本题采用子问题思路。先判断root是否为空的情况,然后判断两棵树是否为相同的树,判断subRoot是不是root.left的子树,判断subRoot是不是root.right的子树。
xxxflower
2023/04/16
2700
【力扣/牛客刷题】二叉树篇
二叉树oj以及前中后序非递归写法
给你二叉树的根节点 root ,请你采用前序遍历的方式,将二叉树转化为一个由括号和整数组成的字符串,返回构造出的字符串。
始终学不会
2023/10/17
2340
二叉树oj以及前中后序非递归写法
总结了一些二叉树操作的干货……
导读:二叉树是一种经典的数据结构,其概念本身不难理解,但因其结构的特殊性,许多操作都有着非常精妙的技巧。结合最近LeetCode中的一些相关题目,简要记录一些个人觉得比较巧妙的编程实现。
luanhz
2020/04/01
3130
相关推荐
二叉树基础及实现(二,加经典OJ)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验