LeetCode算法题解|​ 669. 修剪二叉搜索树​、108. 将有序数组转换为二叉搜索树、​538. 把二叉搜索树转换为累加树​

这篇具有很好参考价值的文章主要介绍了LeetCode算法题解|​ 669. 修剪二叉搜索树​、108. 将有序数组转换为二叉搜索树、​538. 把二叉搜索树转换为累加树​。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、LeetCode 669. 修剪二叉搜索树​

题目链接:669. 修剪二叉搜索树

题目描述:

给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意,根节点可能会根据给定的边界发生改变。

示例 1:

LeetCode算法题解|​ 669. 修剪二叉搜索树​、108. 将有序数组转换为二叉搜索树、​538. 把二叉搜索树转换为累加树​,Java算法题解,算法,数据结构,leetcode,java

输入:root = [1,0,2], low = 1, high = 2
输出:[1,null,2]

示例 2:

LeetCode算法题解|​ 669. 修剪二叉搜索树​、108. 将有序数组转换为二叉搜索树、​538. 把二叉搜索树转换为累加树​,Java算法题解,算法,数据结构,leetcode,java

输入:root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出:[3,2,null,1]

提示:

  • 树中节点数在范围 [1, 104] 内
  • 0 <= Node.val <= 104
  • 树中每个节点的值都是 唯一 的
  • 题目数据保证输入是一棵有效的二叉搜索树
  • 0 <= low <= high <= 104
算法分析:

利用递归和回溯思想。

写出两个方法分别找出当前树的最大直节点以及最小值节点。

public TreeNode Max(TreeNode root) {//找出二叉搜索树的最大值节点
        if(root == null) return root;
        else if(root.right != null) return Max(root.right);
        else return root;
    }
    public TreeNode Min(TreeNode root) {//找到二叉搜索树的最小值节点
        if(root == null) return root;
        else if(root.left != null) return Min(root.left);
        else return root;
    }

在递归函数中,

如果当前节点为空,直接返回null。

如果当前节点的值大于目标区间的最大值high,说明当前节点以及右子树的所有节点值都不在区间范围内,剪去当前节点以及右子树。

如果当前节点的值小于目标区间的最小值low,说明当前节点以及左子树的所有节点值都不在目标区间范围内,减去当前节点以及左子树。

如果当前树的最大直小于目标区间最大值high,并且最小值大于目标区间最小值low,即当前树的所有节点值都在目标区间范围内,此时可以直接返回当前树的根节点。

以上四种情况排除之后,当前的情况是,根节点的值再目标区间范围内,但是最小值和最大值两个节点当中至少有一个不在目标区间范围内。

此时我们要分别向左右子树递归去修剪那些不合理的节点,然后再将当前的节点返回就可以啦!

代码如下:

class Solution {
    public TreeNode Max(TreeNode root) {//找出二叉搜索树的最大值节点
        if(root == null) return root;
        else if(root.right != null) return Max(root.right);
        else return root;
    }
    public TreeNode Min(TreeNode root) {//找到二叉搜索树的最小值节点
        if(root == null) return root;
        else if(root.left != null) return Min(root.left);
        else return root;
    }
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null) return null;//如果当前节点为空,直接返null
        else if(root.val > high) return trimBST(root.left, low, high);//如果当前节点的值大于high,那么说明右子树的全部节点值都不在目标区间内,向左递归去寻找合理的节点
        else if(root.val < low) return trimBST(root.right, low, high);//反之如果当前节点的值小于low,说明当前节点及左子树全部节点的值都不在目标区间内,向右递归去寻找合理的节点
        else if(Max(root).val <= high && Min(root).val >= low) return root;//如果当前树的最大值小于等于high并且最小值大于等于low,即当前树在目标区间范围内,则可以直接返回当前树的根节点
        else {//到这儿的情况是,根节点的值在目标区间范围内,儿最大值和最小值至少有一个不在区间范围
            root.left = trimBST(root.left, low, high);//向左子树递归去修剪不合理的节点,再返回左子树的根节点
            root.right = trimBST(root.right, low, high);//向右递归去修剪右子树的不合理节点,在返回根节点
            return root;//此时左右子树都修剪完了,返回当前节点
        }
    }
}

二、 LeetCode108. 将有序数组转换为二叉搜索树

题目链接:108. 将有序数组转换为二叉搜索树
题目描述:

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1:

LeetCode算法题解|​ 669. 修剪二叉搜索树​、108. 将有序数组转换为二叉搜索树、​538. 把二叉搜索树转换为累加树​,Java算法题解,算法,数据结构,leetcode,java

输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:

LeetCode算法题解|​ 669. 修剪二叉搜索树​、108. 将有序数组转换为二叉搜索树、​538. 把二叉搜索树转换为累加树​,Java算法题解,算法,数据结构,leetcode,java

示例 2:

LeetCode算法题解|​ 669. 修剪二叉搜索树​、108. 将有序数组转换为二叉搜索树、​538. 把二叉搜索树转换为累加树​,Java算法题解,算法,数据结构,leetcode,java

输入:nums = [1,3]
输出:[3,1]
解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 按 严格递增 顺序排列

提示:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 按 严格递增 顺序排列
算法分析

根据二叉搜索树的性质(每个节点的做左右子树高度差不超过一),题目给我们的是一个有序的数组。

那么我们每次只去要找道数组的中间元素作为树的根节点,然后将数组从中间分割成两个数组,左数组用来创建左子树,右数组用来创建右子树。

然后向左右数组依次递归下去,最后返回根节点即可。

代码如下:

class Solution {
    public TreeNode BuildTree(int[] nums, int left, int right) {//区间利用左闭右开原则
        if(left >= right) return null;//如果左区间大于等于有区间返回空节点
        if(right - left == 1) return new TreeNode(nums[left]);//如果区间内只有一个元素,将当前元素创建成节点后返回
        else {//区间内有多个元素时
            int mid = left + (right - left) / 2;//找到这段区间内的中间元素
            TreeNode node = new TreeNode(nums[mid]);//将中间元素创建成节点,以该节点为树的根节点
            node.left = BuildTree(nums, left, mid);//利用递归创建左子树
            node.right = BuildTree(nums, mid + 1, right);//利用递归创建右子树
            return node;//返回当前书的根节点
        }
    }
    public TreeNode sortedArrayToBST(int[] nums) {
        return BuildTree(nums, 0, nums.length);
    }
}

三、​538. 把二叉搜索树转换为累加树​

题目链接:538. 把二叉搜索树转换为累加树

题目描述:

给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下,二叉搜索树满足下列约束条件:

  • 节点的左子树仅包含键 小于 节点键的节点。
  • 节点的右子树仅包含键 大于 节点键的节点。
  • 左右子树也必须是二叉搜索树。

注意:本题和 1038: 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 相同

示例 1:

LeetCode算法题解|​ 669. 修剪二叉搜索树​、108. 将有序数组转换为二叉搜索树、​538. 把二叉搜索树转换为累加树​,Java算法题解,算法,数据结构,leetcode,java

输入:[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出:[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2:

输入:root = [0,null,1]
输出:[1,null,1]

示例 3:

输入:root = [1,0,2]
输出:[3,3,2]

示例 4:

输入:root = [3,2,4,1]
输出:[7,9,4,10]

提示:

  • 树中的节点数介于 0 和 104 之间。
  • 每个节点的值介于 -104 和 104 之间。
  • 树中的所有值 互不相同 。
  • 给定的树为二叉搜索树。
算法分析:

利用右中左序遍历,当前节点的是值加等于前一个节点的值。

代码如下:

class Solution {
    int pre = 0;//记录前一个节点的值
    public void midTravel(TreeNode cur) {//右中左序遍历
        if(cur == null) return;
        midTravel(cur.right);
        cur.val += pre;
        pre = cur.val;
        midTravel(cur.left);
    }
    public TreeNode convertBST(TreeNode root) {
        midTravel(root);
        return root;
    }
}

总结

修剪二叉搜索树、构造二叉搜索树、累加树。文章来源地址https://www.toymoban.com/news/detail-740299.html

到了这里,关于LeetCode算法题解|​ 669. 修剪二叉搜索树​、108. 将有序数组转换为二叉搜索树、​538. 把二叉搜索树转换为累加树​的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法刷题Day 23 修剪二叉搜索树+将有序数组转换为二叉搜索树+把二叉搜索树转换为累加树

    递归 好神奇,完全凭感觉写,感觉应该过不了,结果就过了 具体是什么原理可以参考代码随想录的讲解 递归 迭代 使用三个队列来处理(感觉用三个栈也可以) 其实就是以右-中-左的顺序来处理二叉树 每次将当前节点加上上一次访问节点的新值 能想到保存前一次访问节点的

    2024年02月15日
    浏览(41)
  • 【算法题】108. 将有序数组转换为二叉搜索树

    给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 示例 1: 输入:nums = [-10,-3,0,5,9] 输出:[0,-3,9,-10,null,5] 解释:[0,-10,5,null,-3,nul

    2024年02月20日
    浏览(37)
  • 力扣 108 将有序数组转化为二叉搜索树

    目录 题目描述: 代码部分: (1)第一种方法  (2)第二种方法 题目解析: (1)复杂度与思想 (2)进阶分析: 给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高

    2024年02月08日
    浏览(35)
  • 力扣日记1.14-【二叉树篇】108. 将有序数组转换为二叉搜索树

    日期:2023.1.14 参考:代码随想录、力扣 题目描述 难度:简单 给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 示例 1: 输入:

    2024年02月01日
    浏览(38)
  • LeetCode算法题解(动态规划)|LeetCode343. 整数拆分、LeetCode96. 不同的二叉搜索树

    题目链接:343. 整数拆分 题目描述: 给定一个正整数  n  ,将其拆分为  k  个  正整数  的和(  k = 2  ),并使这些整数的乘积最大化。 返回  你可以获得的最大乘积  。 示例 1: 示例 2: 提示: 2 = n = 58 算法分析: 定义dp数组及下标含义: dp[i]表述正整数i拆分成k个正整数

    2024年02月04日
    浏览(40)
  • Leetcode 二叉树 669

    确定好区间的开闭 因为这道题要直接加在nums1里面,所以从后往前 (需不需要resize nums1) 1. 2. 要注意如何保留下来第一个数字 出现的一些错误: 1.记录重复次数的当出现2个的情况时,不需要将dupnum赋值0, 如果赋值0,后面又会重新计数,加进来, 遇到不同的在改为0就可以了

    2024年02月12日
    浏览(35)
  • ( “树” 之 BST) 109. 有序链表转换二叉搜索树 ——【Leetcode每日一题】

    二叉查找树(BST):根节点大于等于左子树所有节点,小于等于右子树所有节点。 二叉查找树中序遍历有序。 给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子

    2023年04月23日
    浏览(39)
  • 【算法与数据结构】700、LeetCode二叉搜索树中的搜索

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :二叉搜索树(Binary Search Tree, BST)的性质:所有左子树节点键值 中间节点键值 所有右子树节点键值,并且左右子树都是二叉搜索树。那么我们根据此性质,对比目标值和中间节点,如

    2024年02月10日
    浏览(40)
  • 【算法刷题day20】Leetcode:654. 最大二叉树、617.合并二叉树、700. 二叉搜索树中的搜索、98.验证二叉搜索树

    草稿图网站 java的Deque 题目: 654. 最大二叉树 解析: 代码随想录解析 解题思路 NLR的建树 代码 总结 暂无 题目: 617.合并二叉树 解析: 代码随想录解析 解题思路 如果都为root1, root2都为空,返回null;如果root1为空,root2不为空,返回root2;如果roo1不为空,root2为空,返回root

    2024年04月10日
    浏览(39)
  • 【算法与数据结构】98、LeetCode验证二叉搜索树

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :注意不要落入下面你的陷阱,笔者本来想左节点键值中间节点键值右节点键值即可,写出如下代码:   在leetcode执行时遇到下面的错误,再次读题,发现是所有左子树的键值小于

    2024年02月09日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包