Invert Binary Tree

Invert a binary tree.

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

to

  1.      4
  2.    /   \
  3.   7     2
  4.  / \   / \
  5. 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 fuck off.

Solution:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.   public TreeNode invertTree(TreeNode root) {
  12.     if (root == null)
  13.       return null;
  15.     invertTree(root.left);
  16.     invertTree(root.right);
  18.     TreeNode tmp = root.left;
  19.     root.left = root.right;
  20.     root.right = tmp;
  22.     return root;
  23.   }
  24. }