Problem Statement:

Invert a binary tree.

Idea:

Here we just use a simple recursive solution. Just swap your children pointers, then call recursively on the children. Eventually everynode will swap the children pointers, and the tree will be inverted.

Solution:

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        swapNodes(root);

        return root;
    }

    void swapNodes(TreeNode *root) {
        if (!root) 
            return;

        std::swap(root->left, root->right);

        swapNodes(root->left);
        swapNodes(root->right);
    }
};

Complexity Analysis:

Time

O(H) where H is the height of the tree.

Memory

O(H) where H is the height of the tree, memory used in the form of stack frames from recursive calls.