Max Tree 126

Question

Given an integer array with no duplicates. A max tree building on this array is defined as follow: 1) The root is the maximum number in the array 2) The left subtree and right subtree are the max trees of the subarray divided by the root number. Construct the max tree by the given array.

Example: Given [2, 5, 6, 0, 3, 1], the max tree is

                                     6
                                   /   \
                                 5      3
                                /      /  \ 
                               2      0    1

Solution

这题要我们用一个数组构建一个Max Tree，其定义与Heap类似，都要求每个节点必须比其子节点大，但是和Heap不同的地方在于Max Tree不要求左边先填满。主要思想为利用单调递减栈，即栈中每个元素都比其右边的元素大。具体方法如下：

1) 如果新来一个数，比堆栈顶的树根的数小，则把这个数作为一个单独的节点压入堆栈。

2) 否则，不断从堆栈里弹出树，新弹出的树以旧弹出的树为右子树，连接起来，直到目前堆栈顶的树根的数大于新来的数。然后，弹出的那些数，已经形成了一个新的树，这个树作为新节点的左子树，最后把这个新树压入堆栈。

这样的堆栈是单调递减的，越靠近堆栈顶的数越小。栈中存储的都是子树的根，且都只有左子树没有右子树。 最后还要按照（2）的方法，把所有树弹出来，每个旧树作为新树的右子树。

代码如下：

*Definition of TreeNode: 
 * public class TreeNode { 
 *     public int val; 
 *     public TreeNode left, right; 
 *     public TreeNode(int val) { 
 *         this.val = val; 
 *         this.left = this.right = null; 
 *     } 
 * }

 public class Solution { 
    /** 
     * @param A: Given an integer array with no duplicates. 
     * @return: The root of max tree. 
     */ 
    public TreeNode maxTree(int[] A) { 
        if (A.length==0) return null; 

        Stack<TreeNode> nodeStack = new Stack<TreeNode>(); 
        nodeStack.push(new TreeNode(A[0])); 
        for (int i=1;i<A.length;i++) 
            if (A[i]<=nodeStack.peek().val){ 
                TreeNode node = new TreeNode(A[i]); 
                nodeStack.push(node); 
            } else { 
                TreeNode n1 = nodeStack.pop(); 
                while (!nodeStack.isEmpty() && nodeStack.peek().val < A[i]){ 
                    TreeNode n2 = nodeStack.pop(); 
                    n2.right = n1; 
                    n1 = n2; 
                } 
                TreeNode node = new TreeNode(A[i]); 
                node.left = n1; 
                nodeStack.push(node); 
            } 

        TreeNode root = nodeStack.pop(); 
        while (!nodeStack.isEmpty()){ 
            nodeStack.peek().right = root; 
            root = nodeStack.pop(); 
        } 

        return root; 
    } 
}