A stack-based C++ solution


  • 0
    vector<int> inorderTraversal(TreeNode* root) {
    	vector<int> ans;
    	vector<pair<TreeNode*, int>> stack;
    	stack.push_back(pair<TreeNode*, int>(root, 0)); 
    	while( !stack.empty() ) {
    		auto e = stack.back();
    		stack.pop_back();
    		if( e.second != 0 ) {
    			if( e.first ) ans.push_back(e.first->val);
    		} else {
    			e.second = 1;
    			if( !e.first ) continue;
    			if( e.first->right ) stack.push_back(pair<TreeNode*, int>(e.first->right, 0)); 
    			stack.push_back(e);
    			if( e.first->left) stack.push_back(pair<TreeNode*, int>(e.first->left, 0)); 
    		}
    	}
    	return ans;
    }
    

    4ms, not fast enough. I checked the results and found most people can make 0ms. Curious how they did it.


  • 0
    J
    This post is deleted!

Log in to reply
 

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