Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:
The root is the maximum number in the array.
The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.
Construct the maximum tree by the given array and output the root node of this tree.
Example 1:
Note:
The size of the given array will be in the range [1,1000].
這道題給了我們一個數組，讓我們建立一個最大二叉樹，建立規則是數組中的最大值為根結點，然後分隔出的左右部分再分别建立最大二叉樹。那麼明眼人一看就知道這是分治法啊，果斷上遞歸啊。首先就是要先找出數組中的最大值，由于數組是無序的，是以沒啥好的辦法，就直接周遊吧，找到了最大值，就建立一個結點，然後将左右兩個子數組提取出來，分别調用遞歸函數并将結果連到該結點上，最後将結點傳回即可，參見代碼如下：
解法一：
<a>class Solution {</a>
下面這種方法也是遞歸的解法，和上面的解法稍有不同的是不必提取子數組，而是用兩個變量來指定子數組的範圍，其他部分均和上面的解法相同，參見代碼如下：
解法二：
下面這種解法是論壇上的高分解法，使用到了一個輔助數組v來讓保持降序。我們周遊數組，對于每個周遊到的數字，建立一個結點，然後進行循環，如果數組v不空，且末尾結點值小于目前數字，那麼将末尾結點連到目前結點的左子結點，并且移除數組中的末尾結點，這樣可以保證子結點都會小于父結點。循環結束後，如果此時數組v仍不為空，說明結點值很大，那麼将目前結點連到數組末尾結點的右子結點上。之後别忘了将目前結點加入數組v中，最後傳回數組v的首結點即可，如果不太容易了解的話，就把題目中的例子帶入一步一步運作看一下吧，參見代碼如下：
解法三：
參考資料：
<a href="https://discuss.leetcode.com/topic/98509/c-o-n-solution">https://discuss.leetcode.com/topic/98509/c-o-n-solution</a>
<a href="https://discuss.leetcode.com/topic/98457/java-c-simple-recursive-method">https://discuss.leetcode.com/topic/98457/java-c-simple-recursive-method</a>
，如需轉載請自行聯系原部落客。