題目
給定一個(gè)二叉搜索樹魂奥，同時(shí)給定最小邊界L 和最大邊界 R。通過(guò)修剪二叉搜索樹易猫，使得所有節(jié)點(diǎn)的值在[L, R]中 (R>=L) 耻煤。你可能需要改變樹的根節(jié)點(diǎn)，所以結(jié)果應(yīng)當(dāng)返回修剪好的二叉搜索樹的新的根節(jié)點(diǎn)准颓。
示例
示例 1
輸入:
1
/ \
0 2
L = 1
R = 2
輸出:
1
\
2
示例 2
輸入:
3
/ \
0 4
\
2
/
1
L = 1
R = 3
輸出:
3
/
2
/
1
解答
【參考官方答案】當(dāng)node.val > R哈蝇，那么修剪后的二叉樹必定出現(xiàn)在節(jié)點(diǎn)的左邊。類似地攘已，當(dāng)node.val < L炮赦，那么修剪后的二叉樹出現(xiàn)在節(jié)點(diǎn)的右邊。否則样勃，我們將會(huì)修剪樹的兩邊吠勘。
class Solution(object):
def trimBST(self, root, L, R):
def trim(node):
if not node:
return None
elif node.val > R:
return trim(node.left)
elif node.val < L:
return trim(node.right)
else:
node.left = trim(node.left)
node.right = trim(node.right)
return node
return trim(root)
如有疑問或建議，歡迎評(píng)論區(qū)留言~
