Java——二叉树的最近公共祖先及二叉搜索树介绍

目录

二叉树的最近公共祖先

题目 

思路一:如果给定的是一颗二叉搜索树,

思路二:假设是孩子双亲表示法

 二叉搜索树

定义Node类

查找

删除

插入


二叉树的最近公共祖先

题目 

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

提示:

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中

思路一:如果给定的是一颗二叉搜索树,

二叉搜索树:中序遍历的大小是有序的,根节点的左树都比根节点的小,根节点的右树都比根节点大。

 

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //先根据二叉搜索树来写
        if(root==null) return null;
        if(root==p||root==q) return root;
        TreeNode leftT=lowestCommonAncestor(root.left,p,q);
        TreeNode rightT=lowestCommonAncestor(root.right,p,q);
        if(leftT!=null&&rightT!=null){
            return root;
        }else if(leftT!=null){
            return leftT;
        }else{
            return rightT;

        }
        
    }
}

思路二:假设是孩子双亲表示法

就相当于链表求交点,但是我们的表示中没有双亲结点,因此我们引入两个栈。

1.用两个栈 存储root->q,root->p的路径;

2.求栈的大小;

3.让栈中多的元素出差值个元素;

4.开始出栈,直到栈顶元素相同,就是公共祖先;

如何去找到从根节点到一个指定节点的路径? 

class Solution {
    //root根结点,node:指定的节点,stack:存放根节点到指定节点的路径
    public boolean getPath(TreeNode root,TreeNode node ,Stack<TreeNode> stack){
        if(root==null||node==null) return false;
        stack.push(root);
        if(node==root) return true;
        boolean flg=getPath(root.left,node,stack);
        if(flg==true) return true;//找到啦
      flg=getPath(root.right,node,stack);
        if(flg==true) return true;//找到啦
        stack.pop();
        return false;

    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        Stack<TreeNode> stack1=new Stack<>();
        getPath(root,p,stack1);
        Stack<TreeNode> stack2=new Stack<>();
        getPath(root,q,stack2);
        int size1=stack1.size();
        int size2=stack2.size();
        if(size1>size2){
            int size=size1-size2;
            while(size!=0){
                stack1.pop();
                size--;
            }
            while(!stack1.isEmpty()&&!stack2.isEmpty()){
                //直接判断地址
                if(stack1.peek()==stack2.peek()){
                    return stack1.pop();
                }else{
                    stack1.pop();
                    stack2.pop();
                }
            }

        }else{
            int size=size2-size1;
            while(size!=0){
                stack2.pop();
                size--;
            }
            while(!stack1.isEmpty()&&!stack2.isEmpty()){
                //直接判断地址
                if(stack1.peek()==stack2.peek()){
                    return stack2.pop();
                }else{
                    stack1.pop();
                    stack2.pop();
                }
            }
        }
        return null;



    }
}

 二叉搜索树

是空树或者:
若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

定义Node类

class Node{
    public int val;
    public Node left;
    public Node right;
    public Node(int val){
        this.val=val;
    }
}

查找

  public Node root=null;
    public Node search(int key){
        Node cur = root;
        if(cur.val<key){
            cur = cur.right;
        }else if(cur.val>key){
            cur = cur.left;
        }else{
            return cur;
        }
        return null;
    }

删除

设待删除结点为 cur, 待删除结点的双亲结点为 parent
1. cur.left == null
1. cur root ,则 root = cur.right
2. cur 不是 root cur parent.left ,则 parent.left = cur.right
3. cur 不是 root cur parent.right ,则 parent.right = cur.right
2. cur.right == null
1. cur root ,则 root = cur.left
2. cur 不是 root cur parent.left ,则 parent.left = cur.left
3. cur 不是 root cur parent.right ,则 parent.right = cur.left
3. cur.left != null && cur.right != null
1. 需要使用 替换法 进行删除,即在它的右子树中寻找中序下的第一个结点 ( 关键码最小 ) ,用它的值填补到被
删除节点中,再来处理该结点的删除问题

   //要删除节点,你需要知道这个节点的父节点
    //当要删除的节点的左节点为空
    //一般删除节点都是删除叶子节点

    public void f(Node cur,Node parent){
        if(cur.left==null){//当删除的节点左边没有节点
            if(cur==root){
                root=cur.right;
            }else if(cur==parent.left){
                parent.left=cur.right;

            }else{
                parent.right=cur.right;

            }
        }else if(cur.right==null){
            if(cur==root){
                root=cur.left;
            }else if(cur==parent.left){
                parent.left=cur.left;
            }else{
                parent.right=cur.left;
            }
        }else{//左右节点都不是空
            //相当于在右树中找一个较小值换到那个位置
            //或者就是在左树中找较大值
            //
            Node targetParent=cur;
            Node target=cur.right;
            while(target.left!=null){
                targetParent=target;
                target=target.left;
            }
            cur.val=target.val;
            if(target==targetParent.left){
                targetParent.left=target.right;
            }else{
                targetParent.right=target.right;
            }
        }


    }
    public void remove(int key){
        Node cur=root;
        Node parent=null;
        while(cur!=null){
            if(cur.val==key){
                f(cur,parent);
                break;
            }else if(cur.val<key){
                parent=cur;
                cur=cur.right;
            }else{
                parent=cur;
                cur=cur.left;
            }

        }
    }

插入

   //二叉搜索树插入的数据一定是在叶子节点
    //1.cur,parent来找到val需要存储的位置
    //2.parent.val比较大小,确定格式在左边还是右边进行插入
    public  boolean insert(int val){
        if(root == null){
            root = new Node(val);
            return true;

        }
        Node cur = root;
        Node parent = null;
        //找到parent的位置
        while(cur!=null){
            if(cur.val<val){
                parent=cur;
                cur=cur.right;
            }else if(cur.val==val){//bu
                return false;
            }else{
                parent=cur;
                cur=cur.left;
            }
        }
        //找到对应位置开始插入
        Node node=new Node(val);
        if(parent.val<val){
            parent.right=node;
        }else{
            parent.left=node;
        }
        return true;

    }

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/436.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

OpenCV入门(十一)快速学会OpenCV 10 形态学操作

OpenCV入门&#xff08;十一&#xff09;快速学会OpenCV 10 形态学操作 作者&#xff1a;Xiou 形态学&#xff0c;即数学形态学&#xff08;Mathematical Morphology&#xff09;&#xff0c;是图像处理过程中一个非常重要的研究方向。 形态学主要从图像内提取分量信息&#…

java入门多线程一文通

一、面试经典 1.为什么使用多线程及其重要 为了使用户体验更好&#xff0c;服务的相应速度更快。现如今硬件不断发展&#xff0c;软件要求也逐渐提高&#xff0c;都是为了一个字&#xff1a;快。 2.进程、线程、管程&#xff08;monitor 监视器&#xff09; 3.多线程并行和…

字符函数和字符串函数(下)——“C”

各位CSDN的uu们你们好呀&#xff0c;今天小雅兰的内容依旧是字符函数和字符串函数呀&#xff0c;这篇博客会讲一些内存相关的函数&#xff0c;下面&#xff0c;让我们进入字符函数和字符串函数的世界吧 字符串查找 strstr strtok 错误信息报告 strerror 字符操作 内存操作函…

微信小程序搭建流程

一、申请微信开发者账号虽然开发微信小程序可以使用工具提供的测试号&#xff0c;但是测试号提供的功能极为有限&#xff0c;而且使用测试号开发的微信小程序不能上架发布。因此说我们想要开发一个可以上架的微信小程序&#xff0c;首先必须要申请微信开发者账号。大家尽可放心…

Python 四大主流 Web 编程框架

目前Python的网络编程框架已经多达几十个&#xff0c;逐个学习它们显然不现实。但这些框架在系统架构和运行环境中有很多共通之处&#xff0c;本文带领读者学习基于Python网络框架开发的常用知识,及目前的4种主流Python网络框架&#xff1a;Django、Tornado、Flask、Twisted。 …

Python带你制作一个属于自己的多功能音乐播放器

前言 嗨喽&#xff0c;大家好呀~这里是爱看美女的茜茜呐 就是用Python做一个简易的音乐播放器&#xff0c;废话不多说&#xff0c;咱们直接开干 当然&#xff0c;今天做这个肯定不是最简单的&#xff0c;最简单的音乐播放器&#xff0c;9行代码足以 完整源码等直接在文末名片领…

什么是API?(详细解说)

编程资料时经常会看到API这个名词&#xff0c;网上各种高大上的解释估计放倒了一批初学者。初学者看到下面这一段话可能就有点头痛了。 API&#xff08;Application Programming Interface,应用程序编程接口&#xff09;是一些预先定义的函数&#xff0c;目的是提供应用程序与开…

SpringCloud Alibaba 学习圣经,10万字实现 SpringCloud 自由

40岁老架构师尼恩的掏心窝&#xff1a; 现在拿到offer超级难&#xff0c;甚至连面试电话&#xff0c;一个都搞不到。 尼恩的技术社群中&#xff08;50&#xff09;&#xff0c;很多小伙伴凭借 “左手云原生右手大数据 SpringCloud Alibaba 微服务“三大绝活&#xff0c;拿到了…

内卷把同事逼成了“扫地僧”,把Git上所有面试题整理成足足24W字Java八股文

互联网大厂更多的是看重学历还是技术&#xff1f;毫无疑问&#xff0c;是技术&#xff0c;技术水平相近的情况下&#xff0c;肯定学历高/好的会优先一点&#xff0c;这点大家肯定都理解。说实话&#xff0c;学弟学妹们找工作难&#xff0c;作为面试官招人也难呀&#xff01;&am…

ChatGPT解答:python大批量读写ini文件时,性能很低,有什么解决方法吗,给出具体的思路和实例

ChatGPT解答&#xff1a; python大批量读写ini文件时&#xff0c;性能很低&#xff0c;有什么解决方法吗&#xff0c;给出具体的思路和实例 ChatGPTDemo Based on OpenAI API (gpt-3.5-turbo). python大批量读写ini文件时&#xff0c;性能很低&#xff0c;有什么解决方法吗&…

让ChatGPT介绍一下ChatGPT

申请新必应内测通过了&#xff0c;我在New Bing中使用下ChatGPT&#xff0c;让ChatGPT介绍一下ChatGPT 问题1&#xff1a;帮我生成一篇介绍chatGPT的文章&#xff0c;不少于2000字 回答&#xff1a; chatGPT是什么&#xff1f;它有什么特点和用途&#xff1f; chatGPT是一种…

【数据结构】链表OJ

Yan-英杰的主页 悟已往之不谏 知来者之可追 目录 ​编辑 ​编辑二、分享&#xff1a;OJ调试技巧 ​编辑三、链表的中间结点 ​编辑四、链表中倒数第k个结点 一、移除链表元素 示例 1&#xff1a; 输入&#xff1a;head [1,2,6,3,4,5,6], val 6 输出&#xff1a;[1,2,3,4,…

世界顶级五大女程序媛,不仅技术强还都是美女

文章目录1.计算机程序创始人&#xff1a;勒芙蕾丝伯爵夫人2.首位获得图灵奖的女性&#xff1a;法兰艾伦3.谷歌经典首页守护神&#xff1a;玛丽莎梅耶尔4.COBOL之母&#xff1a;葛丽丝穆雷霍普5.史上最强游戏程序媛-余国荔说起程序员的话&#xff0c;人们想到的都会是哪些理工科…

springcloud3 GateWay动态路由的案例操作

一 GateWay作用以及流程 1.1 GateWay的作用 gateway相当于所有服务的门户&#xff0c;将客户端请求与服务端应用相分离&#xff0c;客户端请求通过gateway后由定义的路由和断言进行转发&#xff0c;路由代表需要转发请求的地址&#xff0c;断言相当于请求这些地址时所满足的条…

前端前沿web 3d可视化技术 ThreeJS学习全记录

前端前沿web 3d可视化技术 随着浏览器性能和网络带宽的提升 使得3D技术不再是桌面的专利 打破传统平面展示模式 前端方向主要流向的3D图形库包括Three.js和WebGL WebGL灵活高性能&#xff0c;但代码量大&#xff0c;难度大&#xff0c;需要掌握很多底层知识和数学知识 Threej…

【动态规划】最长上升子序列、最大子数组和题解及代码实现

Halo&#xff0c;这里是Ppeua。平时主要更新C语言&#xff0c;C&#xff0c;数据结构算法......感兴趣就关注我吧&#xff01;你定不会失望。 &#x1f308;个人主页&#xff1a;主页链接 &#x1f308;算法专栏&#xff1a;专栏链接 我会一直往里填充内容哒&#xff01; &…

JDK如何判断自己是什么公司的

0x00 前言 因为一些事情&#xff0c;遇到了这样一个问题&#xff0c;JDK如何判断自己是什么公司编译的。因为不同的公司编译出来&#xff0c;涉及到是否商用收费的问题。 平时自己使用的时候&#xff0c;是不会考虑到JDK的编译公司是哪一个&#xff0c;都是直接拿起来用&#…

指针和数组笔试题解析【下篇】

文章目录&#x1f441;️6.指针笔试题&#x1f440;6.1.试题&#xff08;1&#xff09;&#x1f440;6.2.试题&#xff08;2&#xff09;&#x1f440;6.3.试题&#xff08;3&#xff09;&#x1f440;6.4.试题&#xff08;4&#xff09;&#x1f440;6.5.试题&#xff08;5&am…

四边形不等式技巧(上)

文章目录1、引入1.1 题目描述1.2 思路分析1.3 代码实现1.4 小结2、题目二2.1 题目描述2.2 思路分析2.3 代码实现2.4 小结3、题目三&#xff1a;合并石子3.1 题目描述3.2 思路分析3.3 代码实现3.4 枚举优化3.5 对数器4、四边形不等式技巧特征5、应用&#xff1a;画家问题5.1 题目…

金三银四最近一次面试,被阿里P8测开虐惨了...

都说金三银四涨薪季&#xff0c;我是着急忙慌的准备简历——5年软件测试经验&#xff0c;可独立测试大型产品项目&#xff0c;熟悉项目测试流程...薪资要求&#xff1f;5年测试经验起码能要个20K吧 我加班肝了一页半简历&#xff0c;投出去一周&#xff0c;面试电话倒是不少&a…
最新文章