Contents

# 669. Trim a Binary Search Tree

## 題目 :

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node’s descendant should remain a descendant). It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

### Example :

Note

Example 1:

Input: root = [1,0,2], low = 1, high = 2 Output: [1,null,2]

Example 2:

Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3 Output: [3,2,null,1]

Example 3:

Input: root = [1], low = 1, high = 2 Output: [1]

Example 4:

Input: root = [1,null,2], low = 1, high = 3 Output: [1,null,2]

Example 5:

Input: root = [1,null,2], low = 2, high = 4 Output: [2]

#### 解題思路 :

• 這題需要我們為BST做修剪，題目會給我們一個值的範圍，需要我們刪掉不再此數值範圍的node，並回傳這個新的BST
• 根據BST的特性，比當前node數值小的數字都在他的左subtree，比他大的則在他的右subtree，我們可以根據他的特性去做題
• 首先要做的是從root往下找，找到第一個符合該數值範圍的node，他就是我們的新root，所以可以分成三種回傳結束的語句:
1. return trimBST(root.Left, high, low) -> if root.Val > high
2. return trimBST(root.Right, high, low) -> if root.Val < low
3. return root
• 找到我們的新root以後，再讓他們的root.Left 和 root.Right都做同樣的尋找下一個符合數值範圍的node -> recursive
• 以下提供recursive 跟 Iterative版本，因為這題邏輯比較複雜，建議可以先看Iterative版本，能更直白的看懂他的邏輯，再來思考recursive

### Recursive解法

• time complexity: O(log(n)) , space complexity: O(1)

Runtime: 8 ms, faster than 100.00% of Go online submissions for Trim a Binary Search Tree.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 `````` ``````/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func trimBST(root *TreeNode, low int, high int) *TreeNode { if root == nil { return nil } if root.Val < low { return trimBST(root.Right, low, high) } if root.Val > high { return trimBST(root.Left, low, high) } root.Left = trimBST(root.Left, low, high) root.Right = trimBST(root.Right, low, high) return root } ``````

### Iterative解法

• time complexity: O(log(n)) , space complexity: O(1)

Runtime: 8 ms, faster than 100.00% of Go online submissions for Trim a Binary Search Tree.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 `````` ``````/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func trimBST(root *TreeNode, low int, high int) *TreeNode { if root == nil { return nil } for root != nil && (root.Val < low || root.Val > high) { if root.Val < low { root = root.Right }else { root = root.Left } } cur := root for cur != nil { for cur.Left != nil && cur.Left.Val < low { cur.Left = cur.Left.Right } cur = cur.Left } cur = root for cur != nil { for cur.Right != nil && cur.Right.Val > high { cur.Right = cur.Right.Left } cur = cur.Right } return root } ``````