worst case O(n) solution without Recursion


  • 0
    S

    For an DFS / Recursive Solution, the time complexity will be like a partition sort, worst is O(n^2) and average (nlogn)

    However when you think about for each node (or number) , where to find its parent ?
    It will be :
    1) the right child of the first number that is bigger than it in its left side
    2) the left child of the first number that is bigger than it in its right side

    whichever is smaller will be its parent.

    e.g. 3, 2, 1, 6, 0, 5

    for number 2, in its left side, the first number that is bigger than it is 3 and in its right side, the first number that is bigger than it is 6.

    3 is smaller than 6, so 2 will be the right child of 3.

    As for how to find those two number , please look at the following codes for how the stack is operated.

    public class Solution {
        public TreeNode constructMaximumBinaryTree(int[] nums) {
            if (nums == null) return null;
            
            ArrayDeque<TreeNode> stack = new ArrayDeque<>();
            
                  
            for (int i = 0; i < nums.length; i++) {
                TreeNode current = new TreeNode(nums[i]);
                while (!stack.isEmpty() && nums[i] > stack.peek().val) {
                    TreeNode node = stack.pop();
                    if (stack.isEmpty() || nums[i] < stack.peek().val) current.left = node;
                    else stack.peek().right = node;
                }
                stack.push(current);
            }
            while (stack.size() > 1) {
                TreeNode top = stack.pop();
                stack.peek().right = top;
            }
            
            return stack.peek();
        }
    }
    

Log in to reply
 

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