654. Maximum Binary Tree

Problem 654

https://leetcode.com/problems/maximum-binary-tree/ Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

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.

Construct the maximum tree by the given array and output the root node of this tree.

Example 1:

Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1

Solution

左邊最大的就會是 node.left，右邊最大的就會是 node.right 用 recursive 的方式讓相同的邏輯重複去指定，直到結尾

用 stack 的方式，按照順序存入，不停更新 原本在右邊的一定會是（比較小時） node.right 或是（比較大時）其上方的 parent-node，原本在左邊的也是同理。

recusive

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def constructMaximumBinaryTree(self, nums):
        if not nums: return None
        l, r = 0, len(nums) - 1
        root = nums.index( max(nums) )
        node = TreeNode( nums[root] )
        node.left = self.constructMaximumBinaryTree( nums[:root] )
        node.right = self.constructMaximumBinaryTree( nums[root+1:] )

        return node

stack

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def constructMaximumBinaryTree(self, nums):
        stack = []
        for num in nums:
            node = TreeNode(num)
            while stack and stack[-1].val < num:
                node.left = stack.pop()
            if stack:
                stack[-1].right = node
            stack.append(node)
        return stack[0]