首页 > 其他分享 >669. 修剪二叉搜索树(leetcode)

669. 修剪二叉搜索树(leetcode)

时间:2024-05-11 14:09:59浏览次数:25  
标签:669 删除 leetcode high low trimBST 二叉 root 节点

https://leetcode.cn/problems/trim-a-binary-search-tree/description/

要点是区分在区间左边还是右边,在区间左边那么右子树也还有必要去查找删除,右边同理,返回的是删除后新树的根节点

要注意函数要实现单层逻辑和完成闭环语义

class Solution {

    // 查找要删除的节点,进行删除,返回删除节点后新的树的根节点
    public TreeNode trimBST(TreeNode root, int low, int high) {
        // 1.找不到要删除的节点,也顺便删除上一层递归要删除的节点
        if(root==null)return null;
        // 2.节点在边界左边,直接删除此节点,因为左子树都小于根节点,因此尝试查找右子树,返回新树根节点
        if(root.val < low)
        {
            // 搜索右子树
            return trimBST(root.right,low,high);
        }
        // 3.节点在边界右边,直接删除此节点,右子树都大于根节点,因此尝试左子树,返回新树根节点
        if(root.val > high)
        {
            // 搜索左子树
            return trimBST(root.left,low,high);
        }
        // 赋值新树的根节点
        root.left=trimBST(root.left,low,high);
        root.right=trimBST(root.right,low,high);
        return root;
    }

}

 

标签:669,删除,leetcode,high,low,trimBST,二叉,root,节点
From: https://www.cnblogs.com/lxl-233/p/18186388

相关文章

  • 450. 删除二叉搜索树中的节点(leetcode)
    https://leetcode.cn/problems/delete-node-in-a-bst/要点是确定函数语义,单层递归逻辑,确定好有返回值的这种写法,分析出5种情况,递归的时候接收好递归的返回的新树的根节点即可classSolution{//函数语义(单层递归逻辑):查找要删除的节点,并且返回删除节点后新的树的......
  • [LeetCode] 最短的桥 双BFS Java
    Problem:934.最短的桥目录思路复杂度Code思路先找到第一个岛屿,根据每一个岛屿的岛屿块的位置多源查找这个块与第二个岛屿的距离,先找到的就是最少的距离同时,将已遍历过的岛屿标记为-1,避免重复入队复杂度时间复杂度:添加时间复杂度,示例:$O(n^2)$空间复杂度:添......
  • LeetCode 1186. Maximum Subarray Sum with One Deletion
    原题链接在这里:https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/description/题目:Givenanarrayofintegers,returnthemaximumsumfora non-empty subarray(contiguouselements)withatmostoneelementdeletion. Inotherwords,youwa......
  • LeetCode 2210. Count Hills and Valleys in an Array
    原题链接在这里:https://leetcode.com/problems/count-hills-and-valleys-in-an-array/description/题目:Youaregivena 0-indexed integerarray nums.Anindex i ispartofa hill in nums iftheclosestnon-equalneighborsof i aresmallerthan nums[i].......
  • 235. 二叉搜索树的最近公共祖先(leetcode)
    https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/要点是如果root是在p和q之间的值,意味着已经找到了最近公共祖先/***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*rig......
  • 236. 二叉树的最近公共祖先(leetcode)
    https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/要点是后序遍历,这样就可以从树底开始搜索,寻找最近公共祖先classSolution{public://返回的是最近公共祖先,若返回null则说明没有TreeNode*lowestCommonAncestor(TreeNode*r......
  • leetCode 001.两数之和
    给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值target的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。示例1:输入:nums=[2,7,11,15],ta......
  • LeetCode 049. 字母异位词分组
    给你一个字符串数组,请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。示例1:输入:strs=["eat","tea","tan","ate","nat","bat"]输出:[["bat"],["nat","tan"],["......
  • leetCode 128. 最长连续序列
    给定一个未排序的整数数组nums,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。请你设计并实现时间复杂度为O(n)的算法解决此问题。示例1:输入:nums=[100,4,200,1,3,2]输出:4解释:最长数字连续序列是[1,2,3,4]。它的长度为4。示例2:输入:nums=[0,3,7,......
  • Leetcode --- 203. 移除链表元素
    题目描述给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val==val 的节点,并返回 新的头节点 。示例1: 示例输入:head=[1,2,6,3,4,5,6],val=6输出:[1,2,3,4,5]输入:head=[7,7,7,7],val=7输出:[]参考实现方式1、使用递归实现......