leetcode 669 修剪二叉搜索树

╰+攻爆jí腚メ 2022-09-12 08:49 151阅读 0赞

## 前言 ##

题目：[669. 修剪二叉搜索树][669.]

参考题解：[修剪二叉搜索树-力扣官方题解][-]

--------------------

## 提交代码 ##

看到这道题目的时候，我想到的是：遍历二叉树，遍历过程，使用[leetcode 450 删除二叉搜索树中的节点][leetcode 450]删除节点。

但是题目要求，相对不改变原来树结构，所以上面的方法做不到。

想不出来，我去看答案。答案并没有采用删除的方式修剪二叉树。而是，将满足要求的节点重新拼凑成一颗新的树。

下面代码来自参考题解。

class Solution {
    public:
        TreeNode* trimBST(TreeNode* root, int low, int high) {
            // 三个递归出口
            if(root == nullptr)
                return nullptr;
            if(root->val < low)
                return trimBST(root->right,low,high); // 中间小于low，整个左子树和根丢弃
            if(root->val > high)
                return trimBST(root->left,low,high); // 中间大于high，整个右子树和根丢弃
            
            // 根节点得以保存
    
            root->left = trimBST(root->left,low,high);
            root->right = trimBST(root->right,low,high);
            return root;
        }
    };

[669.]: https://leetcode-cn.com/problems/trim-a-binary-search-tree/
[-]: https://leetcode-cn.com/problems/trim-a-binary-search-tree/solution/xiu-jian-er-cha-sou-suo-shu-by-leetcode/
[leetcode 450]: https://blog.csdn.net/sinat_38816924/article/details/120431044

发表评论取消回复

表情：

评论列表（有 0 条评论，151人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode_二叉搜索树_简单_700.二叉搜索树中的搜索

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给定二叉搜索树（BST）的根节点 root 和一个整数值 val。你需要在 BST

向右看齐/ 2023年10月06日 22:23/ 0 赞/ 4 阅读

相关修剪二叉搜索树

修剪二叉搜索树问题： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM

ゞ浴缸里的玫瑰/ 2023年10月06日 08:11/ 0 赞/ 28 阅读

相关 2021-03-12 | 669. 修剪二叉搜索树

1. 题目描述给你二叉搜索树的根节点 `root` ，同时给定最小边界`low` 和最大边界 `high`。通过修剪二叉搜索树，使得所有节点的值在`[low, high

系统管理员/ 2022年11月12日 01:47/ 0 赞/ 131 阅读

相关 Trim a Binary Search Tree（C++修剪二叉搜索树）

解题思路：（1）递归，如果根节点小于下界，只用修剪右子树（2）如果根节点大于上界，只用修剪左子树 / Definition for a binar

小鱼儿/ 2022年11月07日 01:44/ 0 赞/ 139 阅读

相关 LeetCode | 0669. 修剪二叉搜索树【Python】

问题 [力扣][Link 1] 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在\[low, h

雨点打透心脏的1/2处/ 2022年11月03日 10:37/ 0 赞/ 148 阅读

相关【LeetCode】二叉树问题：二分搜索树

二分搜索树 [235. 二叉搜索树的最近公共祖先][235.] 难度简单532收藏分享切换为英文接收动态反馈给定一个二叉搜索树, 找到该树中两个指定节点的最近公

快来打我*/ 2022年10月29日 09:12/ 0 赞/ 192 阅读

相关 leetcode 669 修剪二叉搜索树

前言题目：[669. 修剪二叉搜索树][669.] 参考题解：[修剪二叉搜索树-力扣官方题解][-] -------------------- 提交代码看

╰+攻爆jí腚メ/ 2022年09月12日 08:49/ 0 赞/ 152 阅读

相关 669 修剪二叉搜索树（递归修改）

1. 问题描述：给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在\[low, high\]中。修剪树

心已赠人/ 2022年09月02日 11:36/ 0 赞/ 296 阅读

相关二叉树2---修剪二叉树线索树

1、题目： -------------------- Given a binary search tree and the lowest and highest bound

曾经终败给现在/ 2022年05月25日 11:24/ 0 赞/ 196 阅读

相关 [LeetCode] 二叉搜索树判定

出处 > [验证二叉搜索树][Link 1] 分析 > 给定一个二叉树，判断其是否是一个有效的二叉搜索树。 > 假设一个二叉搜索树具有如下特征： > \-

妖狐艹你老母/ 2022年05月18日 10:11/ 0 赞/ 198 阅读