654. Maximum Binary Tree

Problem:

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

7/9/2018 update:
Finally went through the stack solution. Maintain a increasing stack from top to bottom.

If current node's val is greater than stack top, then pop stack add poped node to current's left. By doing so, we add previous smaller nodes to current's left.

If stack is not empty after the above process. stack pop node's value is greater than current node's value, so current node is on the right of stack top. When inserting 5, after popping 0, 6 left in the stack. 5 should on the right of 6.

stack方法速度也没提示啊，还是13ms.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        Deque<TreeNode> stack = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            TreeNode cur = new TreeNode(nums[i]);
            while (!stack.isEmpty() && stack.peek().val < nums[i]) {
                cur.left = stack.pop();
            }
            if (!stack.isEmpty()) {
                stack.peek().right = cur;
            }
            stack.push(cur);
        }    
        return stack.isEmpty() ? null : stack.removeLast();
    }
}

--------------------------------------------------------------------------------------------------------------------------
Analysis:
用O(n^2)的方法，每次拆分数组找当前范围的最大值。有一种方法是用stack, 是O(n) ，但是面试的时候绝对想不出来，看看就好。

Solution:

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null) return null;
        return helper(nums, 0, nums.length - 1);
    }
    private TreeNode helper(int[] nums, int start, int end) {
        if (start > end) return null;
        int[] max = findMax(nums, start, end);
        TreeNode root = new TreeNode(max[1]);
        root.left = helper(nums, start, max[0] - 1);
        root.right = helper(nums, max[0] + 1, end);
        return root;
    }

    private int[] findMax(int[] nums, int start, int end) {
        int[] res = new int[2];
        res[0] = start;
        res[1] = nums[start];
        for (int i = start; i <= end; i++) {
            if (nums[i] > res[1]) {
                res[1] = nums[i];
                res[0] = i;
            }
        }
        return res;
    }
}