My non-recursive solution, use a stack instead of resursion


  • 1
    D

    My idea is simple. For each node, I build it's left child first.Then build it's left child's left child....Build a stack to store the node I have built. When the iteration reached left corner of the tree, trace back the stack and build right child for each node.
    How do we find the left corner ? The first element of inorder-traverse-array is the left corner of the tree.
    Here is my solution.

    class Solution {
    public:
    	TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    		if (preorder.empty())
    			return NULL;
    		TreeNode* now = new TreeNode(preorder.front());
    		preorder.erase(preorder.begin());
    		stack<TreeNode*> s;
    		s.push(now);
    		while (true){
    			if (s.top()->val == inorder.front()){
    				//build right child and store
                            //the first element of the inorder-array is left corner
    				TreeNode* store = NULL;
    				while (!s.empty() && s.top()->val == inorder.front()){
    					store = s.top();
    					s.pop();
    					inorder.erase(inorder.begin());
    				}
    				if (inorder.empty())
    					break;
    				TreeNode *temp = new TreeNode(preorder.front());
    				preorder.erase(preorder.begin());
    				store->right = temp;
    				s.push(temp);
    			}
    			else{
    				//build left child and store
    				TreeNode *temp = new TreeNode(preorder.front());
    				preorder.erase(preorder.begin());
    				s.top()->left = temp;
    				s.push(temp);
    			}
    		}
    		return now;
    	}
    };

Log in to reply
 

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