654. Maximum Binary Tree

// LeetCode URL: https://leetcode.com/problems/maximum-binary-tree/
import java.util.Stack;

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

/**
 * Refer :
 * https://leetcode.com/problems/maximum-binary-tree/discuss/106156/Java-worst-case-O(N)-solution/143674
 *
 * Time Complexity: O(N). Each TreeNode will be created once, and will be put
 * into the stack and move out of the stack once for worst case. So the time
 * complexity is O(N).
 *
 * Space Complexity: O(N). In worst case, if the array is in descending order.
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }

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

        for (int n : nums) {
            TreeNode cur = new TreeNode(n);

            while (!stack.isEmpty() && stack.peek().val < n) {
                cur.left = stack.pop();
            }

            if (!stack.isEmpty()) {
                stack.peek().right = cur;
            }

            stack.push(cur);
        }

        return stack.isEmpty() ? null : stack.get(0);
    }
}