Binary Tree Postorder Traversal

07/13/2016 Tree Stack

Question

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:

Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution

Result: Accepted Time: 4 ms

Here should be some explanations.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<int> ista;
        stack<TreeNode*> tsta;
        vector<int> ret;
        TreeNode * tmp;
        int lev;
        tsta.push(root);
        ista.push(1);
        while(!tsta.empty())
        {
            tmp = tsta.top();tsta.pop();
            lev = ista.top();ista.pop();
            if(tmp == NULL) continue;
            if(lev == 2)
                ret.push_back(tmp->val);
            else
            {
                tsta.push(tmp),ista.push(2);
                tsta.push(tmp->right),ista.push(1);
                tsta.push(tmp->left),ista.push(1);
            }
        }
        return ret;
    }
};

Complexity Analytics

  • Time Complexity:
  • Space Complexity: