trimBST

Leetcode

基础的剪枝算法，遇到结点值小于L时，返回右子树；遇到结点值大于R时，返回左子树。
否则一切照旧。最后返回结点。

'''
# File: trimBST.py
# Author: 0HP
# Date: 20200217
# Purpose: solve the problem in website:
# https://leetcode.com/problems/trim-a-binary-search-tree/
'''
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def trimBST(self, root: TreeNode, L: int, R: int) -> TreeNode:
        if root==None:
            return None
        if root.val<L:
            return self.trimBST(root.right,L,R)
        elif root.val>R:
            return self.trimBST(root.left,L,R)
        else:
            root.left=self.trimBST(root.left,L,R)
            root.right=self.trimBST(roor.right,L,R)
            return root