問題
給你二叉搜索樹的根節(jié)點(diǎn) root 扣墩，同時給定最小邊界low 和最大邊界 high嗽上。通過修剪二叉搜索樹辜王，使得所有節(jié)點(diǎn)的值在[low, high]中级乐。修剪樹不應(yīng)該改變保留在樹中的元素的相對結(jié)構(gòu)（即，如果沒有被移除尤蛮，原有的父代子代關(guān)系都應(yīng)當(dāng)保留）媳友。 可以證明，存在唯一的答案产捞。
所以結(jié)果應(yīng)當(dāng)返回修剪好的二叉搜索樹的新的根節(jié)點(diǎn)庆锦。注意，根節(jié)點(diǎn)可能會根據(jù)給定的邊界發(fā)生改變轧葛。
示例 1：
image
輸入：root = [1,0,2], low = 1, high = 2
輸出：[1,null,2]
示例 2：
image
輸入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
輸出：[3,2,null,1]
示例 3：
輸入：root = [1], low = 1, high = 2
輸出：[1]
示例 4：
輸入：root = [1,null,2], low = 1, high = 3
輸出：[1,null,2]
示例 5：
輸入：root = [1,null,2], low = 2, high = 4
輸出：[2]
提示：
- 樹中節(jié)點(diǎn)數(shù)在范圍 [1, 104] 內(nèi)
- 0 <= Node.val <= 104
- 樹中每個節(jié)點(diǎn)的值都是唯一的
- 題目數(shù)據(jù)保證輸入是一棵有效的二叉搜索樹
- 0 <= low <= high <= 104
思路
遞歸
只需考慮根節(jié)點(diǎn)需要做什么，其他的交給遞歸艇搀。
代碼
Python3
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
if not root:
return
# 只需考慮根節(jié)點(diǎn)需要做什么尿扯，其他的交給遞歸
# 左邊的全部小于low，所以都剪枝
if root.val < low:
root = root.right
root = self.trimBST(root, low, high)
# 右邊的全部大于high焰雕，所以都剪枝
elif root.val > high:
root = root.left
root = self.trimBST(root, low, high)
else:
root.left = self.trimBST(root.left, low, high)
root.right = self.trimBST(root.right, low, high)
return root
