A generic way to convert recursive method to iterative one.


  • 0
    S

    There's a generic way to convert recursive method to iterative one. See the c++ code below. The three states correspond to three parts (divided by two recursive calls) in the recursive method.

    Recursive:

    void inorderRecursive(TreeNode* root) {
    	// state 0:
    	if (!root) return;
    	inorderRecursive(root->left);
    
    	// state 1:
    	cout << root->val;
    	inorderRecursive(root->right);
    	
    	// default:
    }
    

    Iterative:

    class Solution {
    public:
    	struct Frame {
    		TreeNode* node;
    		int state;
    		Frame(TreeNode* n) : node(n), state(0) {}
    	};
    
    	vector<int> inorderTraversal(TreeNode* root) {
    		vector<int> ret;
    		stack<Frame> frameStack;
    		frameStack.push(root);
    
    		while (!frameStack.empty()) {
    			TreeNode* curr = frameStack.top().node;
    			int state = frameStack.top().state++;
    			switch (state)
    			{
    			case 0:
    				if (!curr) goto pop_frame; // means return
    				frameStack.push(curr->left);
    				break;
    			case 1:
    				ret.push_back(curr->val);
    				frameStack.push(curr->right);
    				break;
    			default:
    				pop_frame: frameStack.pop();
    			}
    		}
    		return ret;
    	}
    };
    

Log in to reply
 

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