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

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.
- The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1].
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.
|
|
最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!