669.Trim a Binary Search Tree
669.Trim a Binary Search Tree
难度:Easy
给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果应当返回修剪好的二叉搜索树的新的根节点。
示例 1:
1
输入:
2
1
3
/ \
4
0 2
5
6
L = 1
7
R = 2
8
9
输出:
10
1
11
\
12
2
13
示例 2:
14
15
输入:
16
3
17
/ \
18
0 4
19
\
20
2
21
/
22
1
23
24
L = 1
25
R = 3
26
27
输出:
28
3
29
/
30
2
31
/
32
1
Copied!
简单递归:
1
/**
2
* Definition for a binary tree node.
3
* struct TreeNode {
4
* int val;
5
* TreeNode *left;
6
* TreeNode *right;
7
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
* };
9
*/
10
class Solution {
11
public:
12
TreeNode* trimBST(TreeNode* root, int L, int R) {
13
if(!root ) return NULL;
14
if(root->val < L)
15
return root->right? trimBST(root->right, L, R) :NULL;
16
if(root->val > R)
17
return root->left? trimBST(root->left, L, R) :NULL;
18
if(root->val==L)
19
root->left=NULL;
20
if(root->val==R)
21
root->right=NULL;
22
23
// TreeNode* ptr=root;
24
if(root->left) root->left=trimBST(root->left,L, R);
25
if(root->right) root->right=trimBST(root->right, L, R);
26
return root;
27
28
29
}
30
};
Copied!
Copy link