Max Tree

Given an integer array with no duplicates. A max tree building on this array is defined as follow:

• The root is the maximum number in the array
• 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.

<code>    6
   / \
  5   3
 /   / \
2   0   1
</code>

Solution: 用stack来维护在每个数出现前比它大得数。

策略：

When new node comes in, if it is larger than the peek, stack.pop() and at the same time append it as the new node’s left child. until the stack peek is larger than the new node or the stack is empty, at this time, the peek.right = new node. then we push new node into the stack. if the stack is empty when the new node is pushed, the new node is the temporary root.

用7,3,8,2,4,5走一遍就理解了

public TreeNode maxTree(int[] A) {
    if (A == null || A.length == 0) {
        return null;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode root = null;
    for (int i = 0; i < A.length; i++) {
        TreeNode curr = new TreeNode(A[i]);
        while (!stack.isEmpty() && A[i] >= stack.peek().val) {
            TreeNode tmp = stack.pop();
            tmp.right = curr.left;
            curr.left = tmp;
        }
        if (!stack.isEmpty()) {
            stack.peek().right = curr;
        } else {
            root = curr;
        }
        stack.push(curr);
    }
    return root;
}

Share