669.修剪二叉搜索树
题目
给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34示例 1:
输入:
1
/ \
0 2
L = 1
R = 2
输出:
1
\
2
示例 2:
输入:
3
/ \
0 4
\
2
/
1
L = 1
R = 3
输出:
3
/
2
/
1
方法
修剪不在[L,R]范围内的节点，也就是说只保留在该范围内的节点。
- 如果$node.val>R$，修剪后的二叉搜索树应该是node的左侧
- 如果$node.val<L$，修剪后的二叉搜索树应该在node的右侧
- 如果当前node满足要求，则修剪node的左右子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def trimBST(self, root, L, R):
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: TreeNode
"""
def trim(root):
if not root:
return None
elif root.val>R:
return trim(root.left)
elif root.val<L:
return trim(root.right)
else:
root.left=trim(root.left)
root.right=trim(root.right)
return root
return trim(root)
复杂度分析：
- 时间复杂度：O(N)，N是给定树的结点数量，每个结点访问一次
- 空间复杂度：O(N)，尽管不显式的采用额外的空间，但是在最坏的情况下递归的栈回和结点数量一样大