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

2021-09-19 535 words 3 minutes

/leetcode669_binarytree/golang_leetcode.png

Contents

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 :

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
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!