669. Trim a Binary Search Tree

发表于 | 分类于 | |

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.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
> > > Input: 
> > >     1
> > >    / \
> > >   0   2
> > >
> > >   L = 1
> > >   R = 2
> > >
> > > Output: 
> > >     1
> > >       \
> > >        2
> >
> >
> >

>

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
> > > Input: 
> > >     3
> > >    / \
> > >   0   4
> > >    \
> > >     2
> > >    /
> > >   1
> > >
> > >   L = 1
> > >   R = 3
> > >
> > > Output: 
> > >       3
> > >      / 
> > >    2   
> > >   /
> > >  1
> > >  
> > >
> >

题意是想对一个搜索二叉树进行裁剪，使到所有的节点的值都在[L,R]之间，对于不在[L,R]范围的则减掉该支。

还是对树的结构不熟悉，由于刚刚做了一个树的层次遍历题637. Average of Levels in Binary Tree ,所以这道题也就是想着用层次遍历的思想，层次遍历每个节点，然后判断这个节点的值是否在[L,R]之间，如果不在的话就把该节点置为nullptr。但是发现这种思路还得维护每个节点父节点，比较麻烦想不出来。

再看了Discussion之后发现用递归解决还是很简答的。

  1. 判断root的节点是否小于L，如果是，则只有root右子树的值才有可能在[L，R]之间，所以只需要返回root的右子树进行剪裁（递归）后的根节点
  2. 同理，判断root的节点是否大于R，如果是，则只有root左子树的值才有可能在[L，R]之间，所以只需要返回root的左子树进行剪裁（递归）后的根节点
  3. 左节点为对左子树裁剪后的子树（递归）
  4. 右节点为对右子树裁剪后的子树（递归）
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    TreeNode *trimBST(TreeNode *root, int L, int R) {
        if (root == nullptr) return nullptr;
        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;
    }
};