代码随想录算法训练营第二十三天|669. 修剪二叉搜索树

[参考链接]

669. 修剪二叉搜索树

[代码]

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, val=0, left=None, right=None):
 4 #         self.val = val
 5 #         self.left = left
 6 #         self.right = right
 7 class Solution(object):
 8     def trimBST(self, root, low, high):
 9         """
10         :type root: TreeNode
11         :type low: int
12         :type high: int
13         :rtype: TreeNode
14         """
15         if not root:
16             return None
17          # 若当前root节点小于左界：只考虑其右子树，用于替代更新后的其本身，抛弃其左子树整体
18         if root.val < low:
19             return self.trimBST(root.right, low, high)
20         # 若当前root节点大于右界：只考虑其左子树，用于替代更新后的其本身，抛弃其右子树整体   
21         if root.val > high:
22             return self.trimBST(root.right, low, hight)
23         
24         if low <= root.val <= high:
25             root.left = self.trimBST(root.left, low, high)
26             root.right = self.trimBST(root.right, low, high)
27             # 返回更新后的剪枝过的当前节点root
28             return root