題目

給定一個二叉搜索樹，同時給定最小邊界L 和最大邊界 R。通過修剪二叉搜索樹，使得所有節(jié)點的值在[L, R]中 (R>=L) 。你可能需要改變樹的根節(jié)點，所以結果應當返回修剪好的二叉搜索樹的新的根節(jié)點。

示例

示例 1

輸入:

    1
   / \
  0   2

L = 1
R = 2

輸出:

    1
      \
       2

示例 2

輸入:

    3
   / \
  0   4
   \
    2
   /
  1

L = 1
R = 3

輸出:

      3
     / 
   2   
  /
 1

解答

【參考官方答案】當node.val > R，那么修剪后的二叉樹必定出現(xiàn)在節(jié)點的左邊。類似地，當node.val < L，那么修剪后的二叉樹出現(xiàn)在節(jié)點的右邊。否則，我們將會修剪樹的兩邊。

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)

如有疑問或建議，歡迎評論區(qū)留言~