LeetCode #226 Invert Binary Tree 두 갈래 나무 뒤집기

Description: Invert a binary tree.
Example:
Input:

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

Output:

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

Trivia: This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.
제목 묘사: 두 갈래 나무 한 그루를 뒤집다.
예:
입력:

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

출력:

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

참고: 이 질문은 Max Howell의 원래 질문의 계발을 받은 것입니다.
구글: 우리 엔지니어의 90퍼센트가 당신이 작성한 소프트웨어(Homebrew)를 사용하지만, 면접에서 화이트보드에서 두 갈래 나무를 뒤집는 문제를 쓸 수 없습니다. 이것은 너무 엉망입니다.
사고방식: LeetCode #107 Binary Tree Level Order Traversal II 두 갈래 나무의 차원을 따라 II와 유사한 사고방식을 반복하거나 반복적으로 해결하는 시간 복잡도 O(n), 공간 복잡도 O(n)
코드: C++:

/**
 * 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) return root;
        queue q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* cur = q.front();
            q.pop();
            TreeNode* temp = cur -> right;
            cur -> right = cur -> left;
            cur -> left = temp;
            if (cur -> left) q.push(cur -> left);
            if (cur -> right) q.push(cur -> right);
        }
        return root;
    }
};

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode temp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(temp);
        return root;
    }
}

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return root
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root