[Golang][Leetcode][BinaryTree]刷題系列-669-Trim a Binary Search Tree

669. Trim a Binary Search Tree
Level : Medium
原題連結 : Click
題目 :
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 :
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,所以可以分成三種回傳結束的語句:
- return trimBST(root.Left, high, low) -> if root.Val > high
- return trimBST(root.Right, high, low) -> if root.Val < low
- 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.
|
|
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.
|
|
最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!