LeetCode669 Trim a Binary Search Tree

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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.

样例

1
2
3
4
5
6
7
8
9
10
11
12
Input: 
1
/ \
0 2

L = 1
R = 2

Output:
1
\
2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Input: 
3
/ \
0 4
\
2
/
1

L = 1
R = 3

Output:
3
/
2
/
1

思路

修剪一颗二叉搜索树,使其权值都位于$[L, R]$之间。

考虑任意一个结点node。

若其权值小于$L$,根据BST的性质(左子树上所有结点的值均小于它的根节点的值,右子树上所有结点的值均大于它的根节点的值),其左子树(包括node本身)应该被修剪掉,此时node结点应该由被修剪后的右子树替代(即使修剪后的右子树变成空树也无妨)。

同理,若其权值大于$R$,根据BST的性质,其右子树(包括node本身)应该被修剪掉,此时node结点应该由被修剪后的左子树替代。

若权值正好在$[L, R]$区间内,那么node结点不变,继续递归下去修剪左右子树。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int L, int R) {
if (root == nullptr) return root;
if (root->val < L) return trimBST(root->right, L, R);
if (root->val > R) return trimBST(root->left, L, R);
root->left = trimBST(root->left, L, R);
root->right = trimBST(root->right, L, R);
return root;
}
};
分享到 评论