题目描述
翻转一棵二叉树。
示例：
输入：
4 / \ 2 7 / \ / \ 1 3 6 9
输出：
4 / \ 7 2 / \ / \ 9 6 3 1
备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
https://leetcode-cn.com/problems/invert-binary-tree/
解法1
这道题很简单，我们就把每一层节点的左子节点和右子节点交换，递归执行到叶节点即可。我们在图1绘制了节点交换的执行过程，首先我们交换跟节点4的左右子树，这里的交换不是指节点值的交换，而是引用的交换，这样才能让被交换节点的所有子树也都一同交换。接下来，我们递归交换节点7与2的左右子树。
时间复杂度为O(n)，空间复杂度为O(n)。全部代码如下：
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null)
return null;
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}