295. Invert Binary Tree

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

Inverting a binary tree means swapping every left child with its corresponding right child, at every level of the tree.

This is the famous "Homebrew" problem — the one that inspired the tweet "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."

Examples

// Input:  [4,2,7,1,3,6,9]
// Output: [4,7,2,9,6,3,1]
//
//     4              4
//    / \            / \
//   2   7   →     7   2
//  / \ / \       / \ / \
// 1  3 6  9     9  6 3  1