Leetcode題解 Python & C#：Maximum Binary Tree

給一列沒有重複的整數陣列，要建立一個 maximum tree，規則如下，並回傳其 root 。

1.The root is the maximum number in the array.
2.The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.

3.The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

root一定是陣列中最大的，最大值位置左方是左子樹的所有值，右方是右子樹的。

因此把 nums[:maxVal] 傳入到 constructMaximumBinaryTree 就可以得到左方子樹，右方也同理。

如此運作下去，最後會傳入一個空陣列，這就是「中止條件」，所以一遇到就馬上回傳 None 使其停止遞迴。

Python

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        if not nums: return None
        maxIdx = nums.index(max(nums))
        return TreeNode(nums[maxIdx], self.constructMaximumBinaryTree(nums[:maxIdx]), self.constructMaximumBinaryTree(nums[maxIdx+1:]))

C#

public class Solution {
    public TreeNode ConstructMaximumBinaryTree(int[] nums) {
        if(nums.Length == 0){return null;}
        int maxIdx = Array.IndexOf(nums, nums.Max());
        return new TreeNode(nums[maxIdx], 
                            ConstructMaximumBinaryTree(nums.Take(maxIdx).ToArray()),
                            ConstructMaximumBinaryTree(nums.Skip(maxIdx+1).Take(nums.Length-maxIdx+1).ToArray()));
    }
}