Similar non-iterative solution for both preorder and postorder traversal


  • 0
    L

    My solution links the preorder and postorder solution directly.
    First of all, the easy non-iterative solution for preorder traversal using a stack

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> nodes;
        nodes.push(root);
        while(!nodes.empty()) {
            TreeNode* node = nodes.top();
            nodes.pop();
            if(node) {
                ans.push_back(node->val);
                nodes.push(node->right);
                nodes.push(node->left);
            }
        }
        return ans;
    }
    

    Note that the traversal order of preorder is:
    root -> left child -> right child
    while the posorder is
    left child -> right child -> root

    using the same code for preorder we can easily adjust the order to
    root -> right child -> left child
    by switching the order of

    nodes.push(node->right);
    nodes.push(node->left);
    

    to

    nodes.push(node->left);
    nodes.push(node->right);
    

    and this is in fact the reverse order of postorder. Here is the code

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> nodes;
        nodes.push(root);
        while(!nodes.empty()) {
            TreeNode* node = nodes.top();
            nodes.pop();
            if(node) {
                ans.push_back(node->val);
                nodes.push(node->left);
                 nodes.push(node->right);
            }
        }
        // revert ans
        reverse(ans.begin(), ans.end());     
        return ans;
    }

Log in to reply
 

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