LeetCode 669. Trim a Binary Search Tree

撰写于 2018-01-03 修改于 2018-01-21 分类 LeetCode 标签 LeetCode

Question:

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:
Input:

1
2
3
4
5
6
1
/ \
0 2
L = 1
R = 2

Output:

1
2
3
1
\
2

Example 2:
Input:

1
2
3
4
5
6
7
8
9
10
3
/ \
0 4
\
2
/
1
L = 1
R = 3

Output:

1
2
3
4
5
3
/
2
/
1

Solution

The problem is pretty simple, follow the following steps and use recursion method

  • If the val of current node is smaller than L, abandon the left sub-tree and trim its right sub-tree
  • If the val of current node is greater than R, abandon the right sub-tree and trim its left sub-tree
  • Else, recursively trim its left and right sub-tree and return the root

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
"""
if not root:
return None
if root.val < L:
return self.trimBST(root.right, L, R)
elif root.val > R:
return self.trimBST(root.left, L, R)
root.left = self.trimBST(root.left, L, R)
root.right = self.trimBST(root.right, L, R)
return root
Site by GoingMyWay using Hexo & Random
备案号: 粤ICP备16087705号-1

I am a ML and RL research student

Hide