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

分析

这题是大名鼎鼎的 Homebrew 的作者 Max Howell 在 Twitter 上发牢骚的那道题。原始 Tweet 地址：https://twitter.com/mxcl/status/608682016205344768

这题最简单的办法，是层次遍历，每次交换左右子树。

但是，这题也可以用递归解决，代码非常短。

解法1 层次遍历

解法2 递归

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/binary-tree/traversal/invert-binary-tree.html