首页 > 其他分享 >代码随想录训练营|Day 22|235,701,450

代码随想录训练营|Day 22|235,701,450

时间:2022-10-12 05:22:04浏览次数:93  
标签:node TreeNode 22 val 450 随想录 null root 节点

235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

https://assets.leetcode.com/uploads/2018/12/14/binarysearchtree_improved.png

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

https://assets.leetcode.com/uploads/2018/12/14/binarysearchtree_improved.png

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [2,1], p = 2, q = 1
Output: 2

Constraints:

  • The number of nodes in the tree is in the range [2, 105].
  • 109 <= Node.val <= 109
  • All Node.val are unique.
  • p != q
  • p and q will exist in the BST.

cur节点是数值在[p, q]区间中则说明该节点cur就是最近公共祖先了
在遍历二叉搜索树的时候就是寻找区间[p.val, q.val](注意这里是左闭又闭)

那么如果 cur.val 大于 p.val,同时 cur.val 大于q.val,那么就应该向左遍历(说明目标区间在左子树上)。

需要注意的是此时不知道p和q谁大,所以两个都要判断

如果 cur.val 小于 p.val,同时 cur.val 小于 q.val,那么就应该向右遍历(目标区间在右子树)。
剩下的情况,就是cur节点在区间(p.val <= cur.val && cur.val <= q.val)或者 (q.val <= cur.val && cur.val <= p.val)中,那么cur就是最近公共祖先了,直接返回cur。

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;
    }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (true) {
            if (root.val > p.val && root.val > q.val) {
                root = root.left;
            } else if (root.val < p.val && root.val < q.val) {
                root = root.right;
            } else {
                break;
            }
        }
        return root;
    }
}

For Future References

题目链接:https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

文章讲解:https://programmercarl.com/0235.二叉搜索树的最近公共祖先.html


701. Insert into a Binary Search Tree

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

Example 1:

https://assets.leetcode.com/uploads/2020/10/05/insertbst.jpg

Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: Another accepted tree is:

https://assets.leetcode.com/uploads/2020/10/05/bst.jpg

Example 2:

Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]

Example 3:

Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output: [4,2,7,1,3,5]

Constraints:

  • The number of nodes in the tree will be in the range [0, 104].
  • 108 <= Node.val <= 108
  • All the values Node.val are unique.
  • 108 <= val <= 108
  • It's guaranteed that val does not exist in the original BST.

只要遍历二叉搜索树,找到空节点 插入元素就可以了
终止条件就是找到遍历的节点为null的时候,就是要插入节点的位置了,并把插入的节点返回。
把添加的节点返回给上一层,就完成了父子节点的赋值操作了

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;
    }
}

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) // 如果当前节点为空,也就意味着val找到了合适的位置,此时创建节点直接返回。
            return new TreeNode(val);
            
        if (root.val < val){
            root.right = insertIntoBST(root.right, val); // 递归创建右子树
        }else if (root.val > val){
            root.left = insertIntoBST(root.left, val); // 递归创建左子树
        }
        return root;
    }
}

For Future References

题目链接:https://leetcode.com/problems/insert-into-a-binary-search-tree/

文章讲解:https://programmercarl.com/0701.二叉搜索树中的插入操作.html


450. Delete Node in a BST

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

  1. Search for a node to remove.
  2. If the node is found, delete the node.

Example 1:

https://assets.leetcode.com/uploads/2020/09/04/del_node_1.jpg

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.

https://assets.leetcode.com/uploads/2020/09/04/del_node_supp.jpg

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value = 0.

Example 3:

Input: root = [], key = 0
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • 105 <= Node.val <= 105
  • Each node has a unique value.
  • root is a valid binary search tree.
  • 105 <= key <= 105

Follow up: Could you solve it with time complexity O(height of tree)?

有以下五种情况:

  • 第一种情况:没找到删除的节点,遍历到空节点直接返回了

找到删除的节点

  • 第二种情况:左右孩子都为空(叶子节点),直接删除节点, 返回NULL为根节点
  • 第三种情况:删除节点的左孩子为空,右孩子不为空,删除节点,右孩子补位,返回右孩子为根节点
  • 第四种情况:删除节点的右孩子为空,左孩子不为空,删除节点,左孩子补位,返回左孩子为根节点
  • 第五种情况:左右孩子节点都不为空,则将删除节点的左子树头结点(左孩子)放到删除节点的右子树的最左面节点的左孩子上,返回删除节点右孩子为新的根节点。
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;
    }
}

For Future References

题目链接:https://leetcode.com/problems/delete-node-in-a-bst/

文章讲解:https://programmercarl.com/0450.删除二叉搜索树中的节点.html

标签:node,TreeNode,22,val,450,随想录,null,root,节点
From: https://www.cnblogs.com/bluesociety/p/16783199.html

相关文章

  • 2022/10/12线程核心概念
    线程核心概念线程就是独立的执行路径。在程序运行时,即使自己没有创建线程,后台也会有多个线程,如主线程,gc线程。main()称之为主线程,为系统的入口,用于执行整个程序。......
  • 2022美团CTF个人决赛WP
    ReverseROP解析data的ROP,一点一点还原frompwnimport*opcode=open('data','rb').read()opcode_gadget=opcode[0x30+8:]foroffsetinrange(0,len(opcode_g......
  • 2022 最新 Java 基础 面试题(二)
    2022最新Java基础面试题(二)​​下面列出这份Java面试问题列表包含的主题​​​​1、Java中能创建volatile数组吗?​​​​2、volatile能使得一个非原子操作变成原......
  • 【2022-10-11】DRF从入门到入土(九)
    drf之内置认证类BasicAuthenticationRemoteUserAuthenticationSessionAuthentication:session认证 如果前端带着cookie过来,经过session的中间件,如果登录了,在request.use......
  • 【2022.10.11】drf(9)
    今日内容内置认证类内置权限类内置频率类补充Django的配置文件以及每一个配置文件的作用过滤类的其他使用全局异常处理接口文档1......
  • CVPR2022 Oral OGM-GE阅读笔记
    标题:BalancedMultimodalLearningviaOn-the-flyGradientModulation(CVPR2022Oral)论文:https://arxiv.org/abs/2203.15332领域:多模态学习解决本质问题在某些多模态......
  • YACS 2022年9月月赛 甲组 T2 区间交集(三) 题解
    所以说,我又来贴标程了。这题有很多做法,线段树,优先队列$and$删除等等,这里分享一种码量极少的二分做法,主要思路:二分+动归#include<bits/stdc++.h>usingnamespacestd;......
  • YACS 2022年9月月赛 甲组 T1 游戏体验 题解
    目前还没有时间写题解,疯狂复习$CSP$复赛中,这题是个线段树(自己可以探究一下,是动态的)先贴个标程,需要的,请#include<bits/stdc++.h>usingnamespacestd;intn,m,a[10000......
  • 2022 CCPC Henan Provincial Collegiate Programming Contest (2022年CCPC河南省赛)解题
    比赛地址Difficulty后面跟的是我认为的难度,如果和官方题解不一样那么也会给出官方题解的难度。整体难度比预想中的要简单,除了计算几何和大模拟选择跳过,防AK的poly题......
  • 【闲话】2022.10.11
    今天又是考试改不动了才发现std::chrono::system_clock::now().time_since_epoch().count()时间是精确到纳秒的啊(后知后觉我突然在想啊你看不是有一些毒瘤......