226. Invert Binary Tree

Invert a binary tree.

Example:

Input:

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

Output:

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

// Recursion
TreeNode* invertTree(TreeNode* root) { // time: O(n); space: O(n)
    if (!root) return root;
    TreeNode* left = invertTree(root->left);
    root->left = invertTree(root->right);
    root->right = left;
    return root;
}

// Iteration
TreeNode* invertTree(TreeNode* root) { // time: O(n); space: O(n)
    if (!root) return root;
    queue<TreeNode*> q({root});
    while (!q.empty()) {
        TreeNode* t = q.front(); q.pop();
        TreeNode* left = t->left;
        t->left = t->right;
        t->right = left;
        if (t->left) q.push(t->left);
        if (t->right) q.push(t->right);
    }
    return root;
}