[LeetCode] Invert Binary Tree

After reading the quote below the problem, you will be motivated to solve it immediately :-) Well, indeed it is also relative easy. The process of inverting a binary tree is simply 3 steps:

1. Swap the left subtree and the right subtree;
2. Invert the left subtree;
3. Invert the right subtree.

So we immediately have the following simple recursive solution.

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return NULL;
        swap(root -> left, root -> right);
        root -> left = invertTree(root -> left);
        root -> right = invertTree(root -> right);
        return root;
    }
};

Well, you may also want to challenge yourself to solve it iteratively. The iterative solution is basically a level-order traversal. Push all the nodes of the same level to a queue and then swap their left subtree and right subtree and iterate over their subtrees.

The code is as follows.

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return NULL;
        queue<TreeNode*> level;
        level.push(root);
        while (!level.empty()) {
            TreeNode* node = level.front();
            level.pop();
            swap(node -> left, node -> right);
            if (node -> left) level.push(node -> left);
            if (node -> right) level.push(node -> right);
        }
        return root; 
    }
};