[Golang][Leetcode][BinaryTree]刷題系列-654-Maximum Binary Tree

2021-09-05 388 words 2 minutes

/leetcode654_binarytree/golang_leetcode.png

Contents

654. Maximum Binary Tree

Level : Medium

原題連結 : Click

題目 :

You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:

Create a root node whose value is the maximum value in nums.
Recursively build the left subtree on the subarray prefix to the left of the maximum value.
Recursively build the right subtree on the subarray suffix to the right of the maximum value.

Return the maximum binary tree built from nums.

Example :

Note

Example 1:

Input: nums = [3,2,1,6,0,5]

Output: [6,3,5,null,2,0,null,null,1]

Explanation: The recursive calls are as follow:

The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5].
- The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1].
  - Empty array, so no child.
  - The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1].
    - Empty array, so no child.
    - Only one element, so child is a node with value 1.
- The largest value in [0,5] is 5. Left prefix is [0] and right suffix is [].
  - Only one element, so child is a node with value 0.
  - Empty array, so no child.

Example 2:

Input: nums = [3,2,1] Output: [3,null,2,null,1]

解題思路 :

這題的概念可以直接參考 leetcode106題解，一樣是重構binary tree，只是這題直接給你更明確的algorithm，只需要照著他的規範就可以寫出完善的程式
這題是以最大值作為root，以最大值的index為基準，左邊為left subtree，右邊為right subtree
接下來就直接同一個邏輯recursive code寫下去，一樣對subtree們找最大值再分成兩邊…不斷遞迴，最後就得到解答!

Recursive解法

time complexity: O(n^2) , space complexity: O(n)

Runtime: 8 ms, faster than 100.00% of Go online submissions for Maximum Binary 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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func constructMaximumBinaryTree(nums []int) *TreeNode {
    
    if len(nums) == 0 {
        return nil
    }
    
    maxIndex := findMaxIndex(nums)
    
    node := &TreeNode {
        Val: nums[maxIndex],
        Left: constructMaximumBinaryTree(nums[:maxIndex]),
        Right: constructMaximumBinaryTree(nums[maxIndex+1:]),
    }
    
    return node
}

func findMaxIndex(arr []int) int {
    
    max := arr[0]
    
    maxIndex := 0
    
    for i, v := range arr {
        if v > max {
            max = v
            maxIndex = i
        }
    }
    
    return maxIndex
    
}

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