题目: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.
题目分析:对于递归而言,是指从某个模式来不停的返回,想好要每一步的操作,以根节点作为模式的触发点,也就是从根的模式来进行思考,考虑每一步是什么,然后返回什么比较合计。
还要利用搜索树的性质来进行处理。
python代码的实现:
class Solution(object):
def trimBST(self, root, L, R):
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: TreeNode
"""
if root == None:
return None
if root.val < L:
node = self.trimBST(root.right, L, R)
root = node
elif root.val > R:
node = self.trimBST(root.left, L, R)
root = node
else:
node = self.trimBST(root.left, L, R)
root.left = node
node = self.trimBST(root.right, L, R)
root.right = node
return root