写点什么

leetcode 669. Trim a Binary Search Tree 修剪二叉搜索树 (简单)

作者:okokabcd
  • 2022 年 9 月 24 日
    山东
  • 本文字数:788 字

    阅读完需:约 3 分钟

leetcode 669. Trim a Binary Search Tree 修剪二叉搜索树 (简单)

一、题目大意

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


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


示例 1:



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

输出:[1,null,2]


示例 2:



输入: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


来源:力扣(LeetCode)链接:https://leetcode.cn/problems/trim-a-binary-search-tree著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、解题思路

什么是二叉查找树?


二叉查找树(Binary Search Tree,BST)是一种特殊的二叉树:对于每个父节点,其左子树中所有节点的值小于等于父节点的值,其右子树中所有节点的值大于等于父节点的值。


利用二叉查找树的大小关系,我们可以很容易地利用递归进行树的处理。

三、解题方法

3.1 Java 实现

class Solution {    public TreeNode trimBST(TreeNode root, int low, int high) {        if (root == null) {            return root;        }        if (root.val > high) {            return trimBST(root.left, low, high);        }        if (root.val < low) {            return trimBST(root.right, low, high);        }        root.left = trimBST(root.left, low, high);        root.right = trimBST(root.right, low, high);        return root;    }}
复制代码

四、总结小记

  • 2022/9/24 孩子静悄悄,必定在做妖;老人也是

发布于: 刚刚阅读数: 4
用户头像

okokabcd

关注

还未添加个人签名 2019.11.15 加入

一年当十年用的Java程序员

评论

发布
暂无评论
leetcode 669. Trim a Binary Search Tree 修剪二叉搜索树 (简单)_LeetCode_okokabcd_InfoQ写作社区