C++ Non-recursive Non-stack solution, no extra space required


  • 1
    A

    You may have noticed that in most of my posts, I use methods totally different from others. (Of course, what's the point of repetition?)

    If we don't count the space occupied by the tree itself (otherwise what do we return?), then this solution is virtually O(1) space.

    Unfortunately the test framework calls "delete" one by one on each node of the returned tree, which makes it impossible to preallocate the space of all nodes as a contiguous chunk.

    class Solution {
    public:
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            uint e = inorder.size();
            if (!e) return NULL;
            uint n, k, p, o;
            vector<TreeNode*> t(e);
            for (uint i = 0; i < e; i++) {
                t[i] = new TreeNode(inorder[i]);
            }
            for (uint i = 0; i < e; i++, p = n) {
                for (n = 0; preorder[i] != inorder[n]; n++);
                if (!i) o = p = n;
                else if (n < p) t[p]->left = t[n];
                else {
                    for (k = n - 1; k > p && !t[k]->left && !t[k]->right; k--);
                    t[k]->right = t[n];
                }
            }
            return t[o];
        }
    };
    

    If we are allowed to use extra space, then we can speed up with the help of "unordered_map".

    202 / 202 test cases passed.
    Status: Accepted
    Runtime: 15 ms

    class Solution {
    public:
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            uint e = inorder.size();
            if (!e) return NULL;
            uint n, k, p, o;
            vector<TreeNode*> t(e);
            unordered_map<int, uint> m;
            for (uint i = 0; i < e; i++) {
                t[i] = new TreeNode(inorder[i]);
                m[inorder[i]] = i;
            }
            for (uint i = 0; i < e; i++, p = n) {
                n = m[preorder[i]];
                if (!i) o = p = n;
                else if (n < p) t[p]->left = t[n];
                else {
                    for (k = n - 1; k > p && !t[k]->left && !t[k]->right; k--);
                    t[k]->right = t[n];
                }
            }
            return t[o];
        }
    };
    

  • 0

    This is not a O(1) space solution.
    Instead of using a stack, you use a vector of space O(n);
    This is in addition to the TreeNodes you are creating.


  • 0
    A

    @xruzty You are actually right. How could I not notice that!


  • 0
    T

    the code is difficult to read for others, could you plz rename those variables with more "natural" words /abbreviations? that would help us a lot...


Log in to reply
 

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