Java solution without recursion


  • 0
    Z

    Tip is to use stack to store any temp viriables.

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums.length == 0) return null;
        Stack<TreeNode> stack = new Stack<>();
        for (int i = 0; i < nums.length; i++) {
        	if (stack.isEmpty()) {
        	    stack.push(new TreeNode(nums[i]));
        	    continue;
        	}
        	if (nums[i] > stack.peek().val) {
        	    TreeNode temp = new TreeNode(nums[i]);
        	    TreeNode dummy = null;
        	    while (!stack.isEmpty() && stack.peek().val <= nums[i]) {
        		    TreeNode node = stack.pop();
        		    node.right = dummy;
        		    dummy = node;
        	    }
        	    temp.left = dummy;
        	    stack.push(temp);
        	} else {
        	    stack.push(new TreeNode(nums[i]));
        	}
        }
        TreeNode dummy = null;
        while (!stack.isEmpty()) {
        	TreeNode node = stack.pop();
        	node.right = dummy;
        	dummy = node;
        }
        return dummy;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.