Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3}, return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?

First we have the recursive algorithm:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void copyTree (TreeNode *node, vector<int> &nodeValues)
    {
        if (node == NULL)
            return;
        copyTree(node->left, nodeValues);
        copyTree(node->right, nodeValues);
        nodeValues.push_back(node->val);
    }
    vector<int> postorderTraversal(TreeNode *root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        vector<int> nodeValues;
        copyTree(root, nodeValues);
        
        return nodeValues;
    }
};

Then to do the iteratively, we use two stacks and perform a level order traversal:


class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        vector<int> nodeValues;
        if (root == NULL) //if tree is NULL, return null vector
            return nodeValues;
        stack<TreeNode *> s1;
        stack<TreeNode *> s2;
        s1.push(root);
        
        while (!s1.empty())
        {
            TreeNode *node = s1.top();
            s2.push(node);
            s1.pop();
            if (node->left != NULL)
                s1.push(node->left);
            if (node->right != NULL)
                s1.push(node->right);
        }//endwhile
        while (!s2.empty())
        {
            TreeNode *tempNode = s2.top();
            nodeValues.push_back(tempNode->val);
            s2.pop();
        }
        return nodeValues;
    }
};
Advertisements
This entry was posted in LeetCode and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s