leetcode 669. Trim a Binary Search Tree

水深无声 2022-06-09 11:12 175阅读 0赞

# 1.题目 #

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in \[L, R\] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.  
修剪一棵二叉搜索树，使得所有节点的值都在\[L,R\]范围内

Example 1:  
Input:

1
       / \
      0   2

L = 1  
R = 2

Output:

1
      \
       2

Example 2:  
Input:

3
       / \
      0   4
       \
        2
       /
      1

L = 1  
R = 3

Output:

3
         / 
       2   
      /
     1

# 2.分析 #

用递归来实现。从根结点开始，  
如果节点值小于L，则砍掉左子树，只留右子树，对右子树进行修剪  
如果节点值大于R，则砍掉右子树，只留左子树，对左子树进行修剪  
如果节点值位于\[L,R\]范围内，则递归，分别对左右子树进行修剪

# 3.代码 #

TreeNode* trimBST(TreeNode* root, int L, int R) {
        if (root == NULL)
            return root;    
        if (root->val > R)
            return trimBST(root->left, L, R);
        else if (root->val < L)
            return trimBST(root->right, L, R);
        else {
            root->left = trimBST(root->left, L, R);
            root->right = trimBST(root->right, L, R);
            return root;
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关 LeetCode - Medium - 1382. Balance a Binary Search Tree

Topic Divide and Conquer Binary Search Tree Depth-First Search Description

╰+哭是因爲堅強的太久メ/ 2022年10月11日 13:37/ 0 赞/ 181 阅读

相关 Recover Binary Search Tree--LeetCode

题目：Two elements of a binary search tree (BST) are swapped by mistake.Recover the tree wi

喜欢ヅ旅行/ 2022年08月05日 14:23/ 0 赞/ 174 阅读

相关 Unique Binary Search Trees--LeetCode

题目： Given n, how many structurally unique BST's (binary search trees) that store valu

ゞ浴缸里的玫瑰/ 2022年08月05日 14:18/ 0 赞/ 159 阅读

相关 leetcode Binary Search Tree Iterator

题目原题链接：[https://leetcode.com/problems/binary-search-tree-iterator/][https_leetcode.c

素颜马尾好姑娘i/ 2022年08月04日 16:58/ 0 赞/ 175 阅读

相关 leetcode 669. Trim a Binary Search Tree

1.题目 Given a binary search tree and the lowest and highest boundaries as L and R, tri

水深无声/ 2022年06月09日 11:12/ 0 赞/ 176 阅读

相关 leetcode 669. Trim a Binary Search Tree 修建二叉搜索树BST + 深度优先遍历DFS

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tr

矫情吗；*/ 2022年06月03日 06:53/ 0 赞/ 137 阅读

相关 669. Trim a Binary Search Tree

[原题链接][Link 1] / Created by Joe on 2017/12/14. https://leetcode.com/problems/trim

桃扇骨/ 2022年06月03日 02:14/ 0 赞/ 119 阅读

相关 [Leetcode] Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree wit

淡淡的烟草味﹌/ 2021年12月03日 07:25/ 0 赞/ 186 阅读

相关刷题leetcode_669. Trim a Binary Search Tree

二叉搜索树（binary search tree）定义二叉搜索树：二叉树中任何节点的键值一定大于其左子树中每一个节点的键值，并且小于其右子树中每一个节点的键值。

Dear 丶/ 2021年10月09日 03:50/ 0 赞/ 237 阅读