代码随想录 Day22 - 二叉树(八)

简介: 代码随想录 Day22 - 二叉树(八)

235. 二叉搜索树的最近公共祖先

二叉搜索树,顺序查找,找到根节点,


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
        if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
        return root;
    }
}


701. 二叉搜索树中的插入操作

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode newRoot = root;
        TreeNode pre = root;
        while (root != null) {
            pre = root;
            if (root.val > val) {
                root = root.left;
            } else if (root.val < val) {
                root = root.right;
            } 
        }
        if (pre.val > val) {
            pre.left = new TreeNode(val);
        } else {
            pre.right = new TreeNode(val);
        }
        return newRoot;
    }
}


450. 删除二叉搜索树中的节点


  • 第一种情况:没找到删除的节点,遍历到空节点直接返回了
  • 找到删除的节点
  • 第二种情况:左右孩子都为空(叶子节点),直接删除节点, 返回 NULL 为根节点
  • 第三种情况:删除节点的左孩子为空,右孩子不为空,删除节点,右孩子补位,返回右孩子为根节点
  • 第四种情况:删除节点的右孩子为空,左孩子不为空,删除节点,左孩子补位,返回左孩子为根节点
  • 第五种情况:左右孩子节点都不为空,则将删除节点的左子树头结点(左孩子)放到删除节点的右子树的最左面节点的左孩子上,返回删除节点右孩子为新的根节点。


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        root = delete(root,key);
        return root;
    }
    private TreeNode delete(TreeNode root, int key) {
        if (root == null) return null;
        if (root.val > key) {
            root.left = delete(root.left,key);
        } else if (root.val < key) {
            root.right = delete(root.right,key);
        } else {
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            TreeNode tmp = root.right;
            while (tmp.left != null) {
                tmp = tmp.left;
            }
            root.val = tmp.val;
            root.right = delete(root.right,tmp.val);
        }
        return root;
    }
}

目录
相关文章
|
12月前
|
开发框架 JavaScript 前端开发
使用 Node.js 和 Express 构建 Web 应用
【10月更文挑战第2天】使用 Node.js 和 Express 构建 Web 应用
|
8月前
|
知识图谱
RT-DETR改进策略【Conv和Transformer】| 2023 引入CloFormer中的Clo block 双分支结构,融合高频低频信息(二次创新AIFI)
RT-DETR改进策略【Conv和Transformer】| 2023 引入CloFormer中的Clo block 双分支结构,融合高频低频信息(二次创新AIFI)
208 12
RT-DETR改进策略【Conv和Transformer】| 2023 引入CloFormer中的Clo block 双分支结构,融合高频低频信息(二次创新AIFI)
|
前端开发 IDE 开发工具
OpenSumi问题之OpenSumi 对于 VS Code 插件生态要如何支持
OpenSumi问题之OpenSumi 对于 VS Code 插件生态要如何支持
278 6
|
XML JSON Java
java项目中使用protobuf扫盲笔记
最近公司 Java 项目中有用到 protobuf,查了些资料还是一脸迷茫。
|
12月前
|
网络协议 API 网络安全
Web实时通信的学习之旅:轮询、WebSocket、SSE的区别以及优缺点
Web实时通信的学习之旅:轮询、WebSocket、SSE的区别以及优缺点
1449 0
|
运维 负载均衡 监控
服务网格下的东西向与南北向流量管理实践|学习笔记
快速学习服务网格下的东西向与南北向流量管理实践
1708 0
服务网格下的东西向与南北向流量管理实践|学习笔记
|
存储 消息中间件 运维
高可用架构和系统设计思想
本文从研发规范层面、应用服务层面、存储层面、产品层面、运维部署层面、异常应急层面这六大层面去剖析一个高可用的系统需要有哪些关键的设计和考虑
|
消息中间件 架构师 Dubbo
免费下载!《Apache RocketMQ 源码解析》带你深入了解Apache RocketMQ
本书围绕Apache RocketMQ 源码进行多方面分析,包含RocketMQ ACL、RocketMQ 消息轨迹、RocketMQ 多副本之Leader 选主等,带你深入了解Apache RocketMQ。
26205 0
免费下载!《Apache RocketMQ 源码解析》带你深入了解Apache RocketMQ
|
机器学习/深度学习 数据采集 自然语言处理
【机器学习】采集数据、特征工程、建立模型、应用四个阶段的详解(图文解释 超详细)
【机器学习】采集数据、特征工程、建立模型、应用四个阶段的详解(图文解释 超详细)
877 0
|
安全 网络安全 数据安全/隐私保护
导致SSL证书无效的原因有哪些?
如果发现SSL证书失效,首先应该看看证书是不是已经过期。为了保障数据安全,实时验证网站身份真实性,SSL证书的有效期逐年缩短,目前各大浏览器支持的SSL证书有效期都不超过一年。如果发现证书已经过期,需要及时续签或者重新购买证书。
578 0
导致SSL证书无效的原因有哪些?