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;
}
}
