226 Invert Binary Tree

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Solution (recusive)

/**
 * 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) {
        if ( root == NULL ) return root;
        invertTree(root->left);
        invertTree(root->right);
        TreeNode* tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        return root;
    }
};

Solution (iterative)

/**
 * 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) {
        if ( root == NULL ) return root;
        vector<TreeNode*> res(1, root);
        while ( res.size() != 0 ) {
            int nres = res.size();
            vector<TreeNode*> res2;
            for ( int i = 0; i <= nres-1; i++ ) {
                TreeNode* tmp = res[i]->left;
                res[i]->left = res[i]->right;
                res[i]->right = tmp;
                if ( res[i]->left != NULL ) res2.push_back(res[i]->left);
                if ( res[i]->right != NULL ) res2.push_back(res[i]->right);
            }
            res = res2;
        }
        return root;
    }
};