C++ O(N) solution


  • 22
    M

    This solution is inspired by @votrubac
    Here is his brilliant solution
    https://discuss.leetcode.com/topic/98454/c-9-lines-o-n-log-n-map

    The key idea is:

    1. We scan numbers from left to right, build the tree one node by one step;
    2. We use a stack to keep some (not all) tree nodes and ensure a decreasing order;
    3. For each number, we keep pop the stack until empty or a bigger number; The bigger number (if exist, it will be still in stack) is current number's root, and the last popped number (if exist) is current number's right child (temporarily, this relationship may change in the future); Then we push current number into the stack.
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
            vector<TreeNode*> stk;
            for (int i = 0; i < nums.size(); ++i)
            {
                TreeNode* cur = new TreeNode(nums[i]);
                while (!stk.empty() && stk.back()->val < nums[i])
                {
                    cur->left = stk.back();
                    stk.pop_back();
                }
                if (!stk.empty())
                    stk.back()->right = cur;
                stk.push_back(cur);
            }
            return stk.front();
        }
    };
    

    This solution will be slightly faster than normal recursive solution.

    Again, great thanks to @votrubac !!!


  • 0
    Z

    nit: you can remove the variable l, and always assign cur->left with stk.back(), then you can make it a bit more concise


  • 0
    M

    @zqfan
    I have fixed that, thanks!


  • 2
    H

    Brilliant solution. Here is the java version.

        public TreeNode constructMaximumBinaryTree(int[] nums) {
            LinkedList<TreeNode> lklist = new LinkedList<>();
            TreeNode left = null;
            for (int num: nums){
                TreeNode cur = new TreeNode(num);
                while (!lklist.isEmpty() && lklist.peekFirst().val < cur.val){
                    cur.left = lklist.pop();
                }
                
                if (!lklist.isEmpty()){
                    lklist.peekFirst().right = cur;
                }
                lklist.push(cur);
            }
            
            return lklist.peekLast();
        }
    

  • 0
    M

    You can avoid the emptiness checks if you use a sentinel.

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode sentinel(INT_MAX);
        vector<TreeNode*> stk = {&sentinel};
        for (int num : nums) {
            TreeNode* cur = new TreeNode(num);
            while (stk.back()->val < num) {
                cur->left = stk.back();
                stk.pop_back();
            }
            stk.back()->right = cur;
            stk.push_back(cur);
        }
        return stk[1];
    }

  • 0
    M

    @ManuelP
    Good idea, thanks!


  • 0
    C

    I have a similar recursive solution but I think the running time for both your solution and mine should be O(nlogn). Actually the whole process is nothing but making a max Heap, right?

        public TreeNode constructMaximumBinaryTree(int[] nums) {
            if(nums == null || nums.length == 0) {
                return null;
            }
            TreeNode root = new TreeNode(nums[0]);
            for(int i = 1; i < nums.length; i++) {
                root = insert(root, new TreeNode(nums[i]));
            }
            return root;
        }
        
        private TreeNode insert(TreeNode root, TreeNode node) {
            if(root == null) {
                return node;
            }
            if(node.val > root.val) {
                node.left = root;
                return node;
            }
            root.right = insert(root.right, node);
            return root;
        }
    

  • 1
    E

    @cwleoo I'm not sure why you'd say this is similar to a max heap. As for the complexity it actually is O(n) because each element will get added and popped from the stack exactly once


  • 0
    C

    @Ellest Yes, you are right. Each element is added and (possibly) popped from the stack once. So it's O(N). Thank you for your explanation!
    BTW, after review of my code and the stack version, I found my solution can grow up to O(n^2) in the worst case if the tree is skewed. But in the stack version, it don't need to trace back to root in each iteration (while my solution will return root every time), so it is guarenteed O(N) runtime.


  • 0
    E

    @cwleoo Yeah your solutions looks like it's performing a modified insertion sort (I say modified because it's really sorting partitions divided by sequential max values). I really like this stack implementation as it handles the logic required for this problem brilliantly.


Log in to reply
 

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