Invert binary tree – iterative method

This problem is famous due to the wellknown twett, by Max Howell.

I can not say it is hard or easy. Here just provide the iterative method as recursive method is really too easy.

In general,  you just need to swap its left and right for each node. It is natural to think it as a pre-order problem.

Source code as this:

/**
 * 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:
    TreeNode* invertTree(TreeNode* root) {
     //trying to use the pre-order to solve this problem
        stack<TreeNode* > s;
        TreeNode* p = root;
        if(p != nullptr) s.push(p);
 
        while(!s.empty()){
            p = s.top();
            s.pop();
 
            if(p->right != nullptr || p->left != nullptr){
                TreeNode* temp = p->right;
                p->right = p->left;
                p->left = temp;
            }
 
            if(p->right != nullptr) s.push(p->right);
            if(p->left != nullptr) s.push(p->left);
        }
        return root;
    }
};
Advertisements
This entry was posted in Algorithms, Tech. Bookmark the permalink.

Welcome your comments!

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s