The iterative solution is easier than you think!


  • 81
    G

    I din't find iterative solutions discussed in the old Discuss. So, I thought, I will add my solution in here.

    The idea is as follows:

    1. Keep pushing the nodes from the preorder into a stack (and keep making the tree by adding nodes to the left of the previous node) until the top of the stack matches the inorder.

    2. At this point, pop the top of the stack until the top does not equal inorder (keep a flag to note that you have made a pop).

    3. Repeat 1 and 2 until preorder is empty. The key point is that whenever the flag is set, insert a node to the right and reset the flag.

    class Solution {
    public:
        TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
            
            if(preorder.size()==0)
                return NULL;
            
            stack<int> s;
            stack<TreeNode *> st;
            TreeNode *t,*r,*root;
            int i,j,f;
            
            f=i=j=0;
            s.push(preorder[i]);
            
            root = new TreeNode(preorder[i]);
            st.push(root);
            t = root;
            i++;
            
            while(i<preorder.size())
            {
                if(!st.empty() && st.top()->val==inorder[j])
                {
                    t = st.top();
                    st.pop();
                    s.pop();
                    f = 1;
                    j++;
                }
                else
                {
                    if(f==0)
                    {
                        s.push(preorder[i]);
                        t -> left = new TreeNode(preorder[i]);
                        t = t -> left;
                        st.push(t);
                        i++;
                    }
                    else 
                    {
                        f = 0;
                        s.push(preorder[i]);
                        t -> right = new TreeNode(preorder[i]);
                        t = t -> right;
                        st.push(t);
                        i++;
                    }
                }
            }
            
            return root;
        }
    };

  • 0
    P
    This post is deleted!

  • 14
    P

    Thanks for sharing the nice code, I have two feedback (sorry to be a little bit picky):

    1. Looks like stack<int> s; is not useful, so we could remove it.
    2. The description of your first step: 1) Keep pushing the nodes from the inorder into a stack.
      I think you actually mean 'preorder'.

  • 25
    D

    Similar idea. A simpler version.

    class Solution {
    public:
        TreeNode *buildTree(vector<int> &pre, vector<int> &in) {
            int i=0,j=0;
            TreeNode *root=new TreeNode(0x80000000);
            TreeNode *pp=NULL,*ptr=root;
            stack<TreeNode*> sn;sn.push(root);
            while (j<in.size()) {
                if (sn.top()->val==in[j]) {
                    pp=sn.top();
                    sn.pop();
                    j++;
                } else if (pp) {
                    ptr=new TreeNode(pre[i]);
                    pp->right=ptr;pp=NULL;
                    sn.push(ptr);
                    i++;
                } else {
                    ptr=new TreeNode(pre[i]);
                    sn.top()->left=ptr;
                    sn.push(ptr);
                    i++;
                }
            }
            ptr=root->left;delete root;
            return ptr;
        }
    }; 

  • 0
    J

    I think the first step you meant to push the node from preorder instead of inorder.


  • 5
    L

    Similiar idea in cpp.

    ppre and pin are pointers to current item.

    Unlike post and in case, we need to construct tree from head to the tail of these two orders.

    class Solution {
    public:
        TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
            if (preorder.size() == 0) return NULL;
            int ppre = 0, pin = 0;
            TreeNode *root = new TreeNode(preorder.at(ppre++));
            TreeNode *p = NULL;
            stack<TreeNode *> roots;
            roots.push(root);
            
            while (true) {
                if (inorder.at(pin) == roots.top()->val) {
                    p = roots.top();
                    roots.pop();
                    pin++;
                    if (pin == inorder.size()) break;
                    if (roots.size() && inorder.at(pin) == roots.top()->val) continue;
                    p->right = new TreeNode(preorder.at(ppre));
                    ppre++;
                    roots.push(p->right);
                }
                else {
                    p = new TreeNode(preorder.at(ppre));
                    ppre++;
                    roots.top()->left = p;
                    roots.push(p);
                }
            }
            
            return root;
        }
    };

  • 6
    T

    Very nice code !
    Below is my easy to understand recursive solution:

    class Solution {
    public:
        TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
            if (preorder.size() <= 0) return NULL;
            return createTree(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
        }
        
        TreeNode* createTree(vector<int> &preorder, vector<int> &inorder, int preStart, int preEnd, int inStart, int inEnd)
        {
            if (preorder.size() <= 0 || preStart > preEnd || inStart > inEnd) return NULL;
            
            TreeNode *root = new TreeNode(preorder[preStart]);
            
            int index;
            
            for (int i = inStart; i <= inEnd; i++)
            {
                if (inorder[i] == preorder[preStart])
                {
                    index = i;
                    break;
                }
            }
            
            root->left = createTree(preorder, inorder, preStart + 1, preStart + index - inStart, inStart, index-1);
            root->right = createTree(preorder, inorder, preStart + index-inStart+1, preEnd, index+1, inEnd);
            
            return root;
        }
    };
    

  • -4
    M

    Here's a C++ solution using iterators

    class Solution {
    private:
    	TreeNode *buildTreeEx(	vector<int>::iterator preorderBegin, vector<int>::iterator preorderEnd,
    							vector<int>::iterator inorderBegin, vector<int>::iterator inorderEnd )
    	{
    		if (preorderBegin == preorderEnd) { 
    		    return NULL; 
    		}
    
    		TreeNode * root = new TreeNode(*preorderBegin);		
    		preorderBegin++;
    
    		auto rootNode = ::find(inorderBegin, inorderEnd, root->val);
    		int leftSize = ::distance(inorderBegin, rootNode);
    		
    		root->left = buildTreeEx(preorderBegin, preorderBegin + leftSize, inorderBegin, rootNode);
    		root->right = buildTreeEx(preorderBegin + leftSize, preorderEnd, rootNode + 1, inorderEnd);
    
    		return root;	
    	}
    public:
    	TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    
    		if (preorder.size() < 1) {
    			return NULL;
    		}		
    		return buildTreeEx(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
    	}
    };

  • 0
    G

    Did you mean recursive?


  • 0
    T

    Thanks, it is recursive solution!


  • 0
    Z

    Your solution is not a iterator way, but a recursive one.


  • 4
    D

    My accepted solution.

    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        TreeNode* root = NULL;
        int size = preorder.size();
        if(size <= 0) return root;
        root = new TreeNode(preorder[0]);
        if(size == 1) return root;
        
        stack<TreeNode*> s;
        s.push(root);
        
        TreeNode* node;
        int i=0, j=0;
        while(i+1 < size) {
            node = s.top();
            if( node->val != inorder[j]) {
                node->left = new TreeNode(preorder[++i]);
                node = node->left;
                s.push(node);
            }
            else {
                s.pop();
                j++;
                if(s.empty() || inorder[j] != s.top()->val) {
                    node->right = new TreeNode(preorder[++i]);
                    node = node->right;
                    s.push(node);
                }
            }//if
        }//while
        return root;
    }

  • 0
    W

    I have a similar idea but I got Runtime Error. I couldn't find out why.
    Here is my solution.

    class Solution {
    public:
    	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    		if (preorder.size() == 0)
    			return nullptr;
    		TreeNode rootnode(preorder[0]);
    		TreeNode *root = &rootnode;
    		TreeNode *it = root;
    		stack<TreeNode *> s;
    		s.push(root);
    		int j = 0;
    		int flag = 0;
    		if (preorder[0] == inorder[0])
    		{
    			flag = 1;
    			j = 1;
    		}
    		for (int i = 1; i<preorder.size(); i++)
    		{
    			if (flag == 0)
    			{
    				it->left = new TreeNode(preorder[i]);
    				s.push(it->left);
    			}
    			else
    			{
    				it->right = new TreeNode(preorder[i]);
    				s.push(it->right);
    			}
    			if (s.empty() || s.top()->val != inorder[j])
    			{
    				if (flag == 0)
    					it = it->left;
    				else
    					it = it->right;
    				flag = 0;
    			}
    			while (!s.empty() && s.top()->val == inorder[j])
    			{
    				flag = 1;
    				j++;
    				it = s.top();
    				s.pop();
    			}
    		}
    		return root;
    	}
    };
    

    I tested my code with following:

    Solution s;
    vector<int> v1{ 6, 2, 1, 4, 3, 5, 7, 9, 8 };
    vector<int> v2{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    TreeNode* t = s.buildTree(v1, v2);
    cout<<t->left->val<<endl;
    cout << t->val << endl;
    cout << t->left->val << endl;
    

    When I debug it, the pointer t is right, but when I cout some value, t will change. I don't know why.


  • 1
    C

    iterator not iterative...


  • 0
    M

    what is the time complexity? thanks


  • 22
    I

    Java

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
        Stack<TreeNode> s = new Stack<>();
        TreeNode root = new TreeNode(preorder[0]), cur = root;
        for (int i = 1, j = 0; i < preorder.length; i++) {
            if (cur.val != inorder[j]) {
                cur.left = new TreeNode(preorder[i]);
                s.push(cur);
                cur = cur.left;
            } else {
                j++;
                while (!s.empty() && s.peek().val == inorder[j]) {
                    cur = s.pop();
                    j++;
                }
                cur = cur.right = new TreeNode(preorder[i]);
            }
        }
        return root;
    }

  • 0
    X

    there is no need to imp iterative method,it is much more hard to understand than recursive method.


  • 0

    Iterative one is faster than my recursive one. Same idea here.

    class Solution {
    public:
        TreeNode *dfs(vector<int> &pre,int &pp,vector<int> &inorder,int s,int t){
            if (s==t) return NULL;
            int i=s,node=pre[pp++];
            while (inorder[i]!=node) i++;
            TreeNode *root=new TreeNode(node);
            root->left=dfs(pre,pp,inorder,s,i);
            root->right=dfs(pre,pp,inorder,i+1,t);
            return root;
        }
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            /* recursive
            int pp=0;
            return dfs(preorder,pp,inorder,0,inorder.size());
            */
            if (preorder.empty()) return NULL;
            TreeNode *p,*root=new TreeNode(preorder[0]);
            stack<TreeNode*> ss;
            ss.push(root);
            for (int i=1,j=0;i<preorder.size();i++){
                if (ss.empty() || ss.top()->val!=inorder[j]){
                    ss.top()->left = new TreeNode(preorder[i]);
                    ss.push(ss.top()->left);
                }
                else{
                    while (!ss.empty() && ss.top()->val == inorder[j]){
                        p=ss.top();
                        ss.pop();j++;
                    }
                    p->right=new TreeNode(preorder[i]);
                    ss.push(p->right);
                }
            }
            return root;
        }
    };
    

  • 0
    Y

    @chang17 what do you mean iterator not iterative?


  • 3
    W

    @gpraveenkumar Here I provide my understanding on how the iterative solution work.

    • Let's first observe the sequence of inorder traversal.
      1) ####$---##$---0+++
      2) 0: The root node of a tree
      3) #: the left child or grandchildren of root node 0, without right child
      4) $: the left child or grandchildren of root node 0, with a right child or subtree.
      5) --- : represent right subtree of node $
      6) +++: represent right subtree of root node.

    • Let's observe the sequence of preorder traveral
      1) 0$##$###------+++
      2) The symbols are the same.

    • Maintain two pointers: ptrin, ptrpre
      1) ptrpre: always points to the next node that is about to be created.
      2) ptrin: when we keep pushing into stack, ptrin always points to the deepest left child of a subtree. When we keeping popping out nodes, ptrin points to nodes that has no right child, until it points to the root of the right subtree of a node that is just popped out from the stack.

    • Maintain a stack
      1) Similar with the stack in inorder traversal, it always stores the chain of left children in a subtree.
      2) When pushing stack, we are traversing the chain of left children in a subtree, and we keeping creating new node and make it as the left child of the node at stack top.
      3) When poping stack, we always pop out a node that has no right child, until we find a node that has right child (subtree).

    • Maintain a temp pointer, that always points to a node popped from stack, the last node that is popped out from the stack has right child (subtree). So the newly created node will be the right child of temp.

    • Procedures of my algorithm:
      1) Create the root node of the entire tree, record the root node for the purpose of return. Push the root node into the stack.
      2) While we has remaining node to create

    (a) When we enter a new iteration, ptrin always points to the deepest left grandchild of a tree. So as long as we have not reached it, we can safely keep creating new left child (grandchild) for top node at stack. This actually creating the chain of left children for a tree, namely ###$#$0. The newly-created node will be pushed in the stack. So, next created node will be its left child.

    (b) Now, after the previous step, we have reached the deepest left child of a tree. Remember inorder traveral, now we need to retreat from the deepest left child until we find the first node that has a right child or subtree. We use a temp pointer to record the node that has right child, than we create the right child for it. This is achievable, because ptrpre always points to the next node that will be created. In other word, now, the node pointed by ptrpre is the right child. This invariant is ensured by the characteristics of preorder traversal. Remember the symbol presentation: 0$##$###------+++. After we create the left children chain: 0$##$###, now the ptrpre points to the first -, which is the right child of the first node with right child (the second $).
    (c) Repeat step (a) and step (c) until we create all nodes.

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            if(preorder.empty()) return NULL;
            int ppre = 0, pin = 0;
            TreeNode* root = new TreeNode(preorder[ppre++]);
            stack<TreeNode*> stk;
            stk.push(root);
            while(true) {
                while(stk.top()->val != inorder[pin]) {
                    TreeNode* newnode = new TreeNode(preorder[ppre++]);
                    stk.top()->left = newnode;
                    stk.push(newnode);
                }
                TreeNode* node;
                while(!stk.empty() && stk.top()->val == inorder[pin]) {
                    node = stk.top();
                    stk.pop();
                    pin++;
                }
                if(ppre == preorder.size()) break;
                TreeNode* newnode = new TreeNode(preorder[ppre++]);
                node->right = newnode;
                stk.push(newnode);
            }
            return root;
        }
    

Log in to reply
 

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