A traditional solution based on stack. the idea can be used to post-order traversal


  • 0
    F

    Expect for preorder traversal, the other two problems meet the question that how we get the parent node?Same process with preorder, but i use a tricky, insert a node without children. Absolutely,postorder traversal can also use the tricky(of course, there is another very excellent solution)

    the code cost 3ms:

    vector<int> inorderTraversal(TreeNode *root) {
    	vector<int> v;
    	if(!root) return v;
    
    	stack<TreeNode*> s;
    	
    	s.push(root);
    	while(!s.empty())
    	{
    		TreeNode* r = s.top();
    		s.pop();
    		if(!r->left && !r->right)
    		{
    			v.push_back(r->val);
    			continue;
    		}
    		if(r->right) s.push(r->right);
    		s.push(new TreeNode(r->val)); // here....
    		if(r->left) s.push(r->left);
    	}
    	return v;
    }
    

    but this may cost too much memory, update to this(8ms):

    vector<int> inorderTraversal(TreeNode *root) {
    	vector<int> v;
    	if(!root) return v;
    
    	typedef pair<TreeNode*, int> elem;
    	stack<elem> s;
    	
    	s.push(elem(root, 0));
    	while(!s.empty())
    	{
    		elem e = s.top();
    		s.pop();
    		TreeNode* r = e.first;
    		if(!r || (!r->left && !r->right))
    		{
    			v.push_back(r ? r->val : e.second);
    			continue;
    		}
    		if(r->right) s.push(elem(r->right, 0));
    		s.push(elem(NULL, r->val));
    		if(r->left) s.push(elem(r->left, 0));
    	}
    	return v;
    }

Log in to reply
 

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