LeetCode 654 - Maximum Binary Tree

Related: LintCode 126 - Max Tree
LeetCode 998 - Maximum Binary Tree II
LeetCode 654 - Maximum Binary Tree
https://leetcode.com/problems/maximum-binary-tree

iven 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

Note:

1. The size of the given array will be in the range [1,1000].

X.

类似单调栈主要思想是维持一个栈，这个栈里面的元素是要从栈底到栈顶保持递减的:
过程:

扫描数组，将每个元素建立一个节点cur；
每次都要判断当前元素是否比栈顶元素大，如果大，就要一直弹出元素，同时，要将当前元素的左孩子设置成弹出的节点: cur.left = stack.pop()；
弹完栈之后，此时栈中的元素都比cur大，此时我们让栈顶的节点的右孩子指向cur；
然后压栈当前元素；
最后返回的是栈底的元素(最大的元素作为根)；
https://github.com/cherryljr/LeetCode/blob/master/Maximum%20Binary%20Tree.java

Approach 2: Using Stack to find the first bigger number in the left/right side.
This question is like constructing a MaxHeap. 
We all know that the time complexity of constructing a MaxHeap is O(n).
So is there a O(n) solution to solve this problem ? Of course, it does.
The key idea is:
    1. We scan numbers from left to right, build the tree one node by one step;
    2. We use a stack to keep some (not all) tree nodes and ensure a decreasing order;
    3. For each number, we keep pop the stack until empty or a bigger number; 
    The bigger number (if exist, it will be still in stack) its right child is current number, 
    and the last popped number (if exist) is current number's left child (temporarily, this relationship may change in the future); 
    Then we push current number into the stack.
Complexity Analysis
    Time  complexity : O(n). We only traverse the array once.
    Space complexity : O(n). The size of stack is n.

  public TreeNode constructMaximumBinaryTree(int[] nums) {

    if (nums == null || nums.length == 0) {

      return null;

    }

    Stack<TreeNode> stack = new Stack<>();

    for (int i = 0; i < nums.length; i++) {

      TreeNode curr = new TreeNode(nums[i]);

      // if the peek element is smaller than current number,

      // then it would be the left child of current number then pop it.

      while (!stack.isEmpty() && nums[i] > stack.peek().val) {

        curr.left = stack.peek();

        stack.pop();

      }

      // the bigger number's (if exist) right chhild is current number.

      if (!stack.isEmpty()) {

        stack.peek().right = curr;

      }

      stack.push(curr);

    }

    // get the buttom element of stack (the largest one)

    TreeNode rst = null;

    while (!stack.isEmpty()) {

      rst = stack.pop();

    }

    return rst;

  }

https://cyleft.com/?p=648

用了一个栈，右子树入栈，当出现左子树需求的时候，一步步弹栈，直到找到值最接近的栈内元素，作为左子树，并弹出此数，将有左子树需求的数入栈，继续往复。

[3 2 1 6 0 5]
栈       树
[]
==========================
[3]       3
==========================
[3,2]      3
            2
==========================
[3,2,1]     3
             2
              1
==========================
[6]          6
            3
             2
              1
==========================
[6,0]       6
             0
==========================
[6,5]       6
              5
             0




    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        vector<TreeNode*> stk;
        for (int i = 0; i < nums.size(); ++i)
        {
            TreeNode* cur = new TreeNode(nums[i]);
            while (!stk.empty() && stk.back()->val < nums[i])
            {
                cur->left = stk.back();
                stk.pop_back();
            }
            if (!stk.empty())
                stk.back()->right = cur;
            stk.push_back(cur);
        }
        return stk.front();
    }

https://leetcode.com/problems/maximum-binary-tree/discuss/106146/C%2B%2B-O(N)-solution
https://discuss.leetcode.com/topic/98454/c-9-lines-o-n-log-n-map-plus-stack-with-binary-search

1. We scan numbers from left to right, build the tree one node by one step;
2. We use a stack to keep some (not all) tree nodes and ensure a decreasing order;
3. For each number, we keep pop the stack until empty or a bigger number; The bigger number (if exist, it will be still in stack) is current number's root, and the last popped number (if exist) is current number's right child (temporarily, this relationship may change in the future); Then we push current number into the stack.

https://leetcode.com/problems/maximum-binary-tree/discuss/106156/Java-worst-case-O(N)-solution

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        Deque<TreeNode> stack = new LinkedList<>();
        for(int i = 0; i < nums.length; i++) {
            TreeNode curr = new TreeNode(nums[i]);
            while(!stack.isEmpty() && stack.peek().val < nums[i]) {
                curr.left = stack.pop();
            }
            if(!stack.isEmpty()) {
                stack.peek().right = curr;
            }
            stack.push(curr);
        }
        
        return stack.isEmpty() ? null : stack.removeLast();
    }

http://www.cnblogs.com/grandyang/p/7513099.html
使用到了一个辅助数组v来让保持降序。我们遍历数组，对于每个遍历到的数字，创建一个结点，然后进行循环，如果数组v不空，且末尾结点值小于当前数字，那么将末尾结点连到当前结点的左子结点，并且移除数组中的末尾结点，这样可以保证子结点都会小于父结点。循环结束后，如果此时数组v仍不为空，说明结点值很大，那么将当前结点连到数组末尾结点的右子结点上。之后别忘了将当前结点加入数组v中，最后返回数组v的首结点即可，如果不太容易理解的话，就把题目中的例子带入一步一步运行看一下吧
https://my.oschina.net/gmxzzz/blog/1862227
用一个栈来存储，如果当前元素比栈顶元素要大，那栈顶元素是当前元素的左子节点；反之，当前元素是栈顶元素的右子节点

  public TreeNode constructMaximumBinaryTree(int[] a) {

    LinkedList<TreeNode> list = new LinkedList<>();

    for (int i = 0; i < a.length; i++) {

      TreeNode curr = new TreeNode(a[i]);

      while (!list.isEmpty() && list.peek().val < a[i]) {

        curr.left = list.pop();

      }

      if (!list.isEmpty()) {

        list.peek().right = curr;

      }

      list.push(curr);

    }

    return list.isEmpty() ? null : list.removeLast();

  }

Just a comment, if we look carefully, the parent of a node = min(nearest max to the left, nearest max to the right) We can use this rule to derive an approach as well using hashmap to store parent->child relationship

X. O(nlogn)
https://discuss.leetcode.com/topic/98433/java-solution-recursion

The idea is to use divide and conquer. Each time we create a node root for the maximum value in the range. Then, we split it into a left range and a right range, which are the left subtree and right subtree of this maximum node root.

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null) return null;
        return build(nums, 0, nums.length - 1);
    }
    
    private TreeNode build(int[] nums, int start, int end) {
        if (start > end) return null;
        
        int idxMax = start;
        for (int i = start + 1; i <= end; i++) {
            if (nums[i] > nums[idxMax]) {
                idxMax = i;
            }
        }
        
        TreeNode root = new TreeNode(nums[idxMax]);
        
        root.left = build(nums, start, idxMax - 1);
        root.right = build(nums, idxMax + 1, end);
        
        return root;
    }

X. Approach #1 Recursive Solution
https://leetcode.com/articles/maximum-binary-tree/

The current solution is very simple. We make use of a function construct(nums, l, r), which returns the maximum binary tree consisting of numbers within the indices $l$ and $r$ in the given $nums$ array(excluding the $r^{th}$ element).

The algorithm consists of the following steps:

1. Start with the function call construct(nums, 0, n). Here, $n$ refers to the number of elements in the given $nums$ array.
2. Find the index, $max_i$, of the largest element in the current range of indices $(l:r-1)$. Make this largest element, $$nums[max_i]$ as the local root node.
3. Determine the left child using construct(nums, l, max_i). Doing this recursively finds the largest element in the subarray left to the current largest element.
4. Similarly, determine the right child using construct(nums, max_i + 1, r).
5. Return the root node to the calling function.

• Time complexity : $O(n^2)$. The function construct is called $n$ times. At each level of the recursive tree, we traverse over all the $n$ elements to find the maximum element. In the average case, there will be a $log(n)$ levels leading to a complexity of $O\big(nlog(n)\big)$. In the worst case, the depth of the recursive tree can grow upto $n$, which happens in the case of a sorted $nums$ array, giving a complexity of $O(n^2)$.
• Space complexity : $O(n)$. The size of the $set$ can grow upto $n$ in the worst case. In the average case, the size will be $log(n)$ for $n$ elements in $nums$, giving an average case complexity of $O(log(n))$

  public TreeNode constructMaximumBinaryTree(int[] nums) {

    return construct(nums, 0, nums.length);

  }

  public TreeNode construct(int[] nums, int l, int r) {

    if (l == r)

      return null;

    int max_i = max(nums, l, r);

    TreeNode root = new TreeNode(nums[max_i]);

    root.left = construct(nums, l, max_i);

    root.right = construct(nums, max_i + 1, r);

    return root;

  }

  public int max(int[] nums, int l, int r) {

    int max_i = l;

    for (int i = l; i < r; i++) {

      if (nums[max_i] < nums[i])

        max_i = i;

    }

    return max_i;

  }