lintcode

image.png

/**
 * 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) {
        // write your code here
        if(A == null || A.length == 0){
            return null;
        }
        Stack<TreeNode> st = new Stack<TreeNode>();
        
        for(int i = 0; i < A.length; i++){
            TreeNode p = new TreeNode(A[i]);
            
            
            if(st.isEmpty() || st.peek().val > p.val){
                st.push(p);
                continue;
            }
            
            TreeNode top = st.pop();
            
            while(!st.isEmpty() && st.peek().val < p.val){
                TreeNode cur = st.pop();
                cur.right = top;
                top = cur;
            }
            p.left = top;
            st.push(p);
        }
        
        TreeNode root = st.pop();
        while(!st.isEmpty()){
            TreeNode cur = st.pop();
            cur.right = root;
            root = cur;
        }
        
        return root;
    }
}