C++ 0ms Recursive and Non-Recursive (DFS Stack) Solution


  • 0
    B

    Recursive solution recurses on left child, then right child, then adds the current node's value to the array.

    The iterative solution uses depth-first search implemented with a stack. Nodes are added as a pair<TreeNode*, bool> with the bool set to false (it's children have not been added to the stack). If the pair at the top of the stack has bool == false, it adds the current pair, the right child pair and left child pair to the stack in that order (i.e. when popped, it will return left->right->parent); if bool == true then it adds the value to the array.

    class Solution {
    public:
        void traverse(TreeNode* curr, vector<int> &vals) {  //recursive solution
            if(curr != NULL) {
                traverse(curr->left, vals);
                traverse(curr->right, vals);
                vals.push_back(curr->val);
            }
        }
    
        vector<int> postorderTraversal(TreeNode* root) {    
            vector<int> vals;
            if (root == NULL) return vals;
            
            //traverse(root, vals);   //recursive solution
            
            stack<pair<TreeNode*, bool>> dfs;   //iterative solution
            dfs.push(pair<TreeNode*, bool>(root, false));
            while (!dfs.empty()) {
                pair<TreeNode*, bool> curr = dfs.top(); dfs.pop();
                if (curr.first != NULL && curr.second == false) {
                    curr.second = true;
                    dfs.push(curr);
                    dfs.push(pair<TreeNode*, bool>(curr.first->right, false));
                    dfs.push(pair<TreeNode*, bool>(curr.first->left, false));
                }
                else if (curr.second == true) {
                    vals.push_back(curr.first->val);
                }
            }
            return vals;
        }
    };
    

Log in to reply
 

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