Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

Inverting a tree means swapping every left node with its corresponding right node.

Function signature

func InvertTree(root *TreeNode) *TreeNode

TreeNode definition

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

Examples

Example 1:

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

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

Example 2:

Input:
  2
 / \
1   3

Output:
  2
 / \
3   1

Example 3:

Input: nil (empty tree)
Output: nil

Example 4:

Input:
  1
 /
2

Output:
  1
   \
    2

Constraints

• The number of nodes in the tree is in the range [0, 100]
• -100 <= Node.val <= 100

Hints

1. Think about what operation you need to do at each node.
2. After swapping children at the current node, do you need to invert the subtrees too?

Notes

• This is a famous problem that became a meme after a developer was rejected for not solving it. Don't be that developer!
• Both recursive and iterative (using a queue) approaches work well.