题目地址：

https://leetcode.com/problems/invert-binary-tree/

翻转二叉树。首先要明确翻转的定义是什么，这里定义是递归的：
1、如果树为空或者只有一个节点，就不翻转
2、否则对调树的左右子树，并翻转左右子树。
翻转，也有一个非递归定义，即：将树的每一层的数的顺序反转。

根据第一种定义，可以用分治法：

public class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return root;}// 翻转左子树，返回其根节点TreeNode left = invertTree(root.left);// 翻转右子树，返回其根节点TreeNode right = invertTree(root.right);// 对调左右子树root.left = right;root.right = left;return root;}
}class TreeNode {int val;TreeNode left, right;TreeNode(int x) {val = x;}
}

时间复杂度$O(n)$，空间复杂度$O(h)$。对于分治法，时间复杂度的计算有一个通用的办法，也就是递推方程。定义一个二叉树的由$l$和$r$构成的序列，$l$表示左子树，$r$表示右子树。例如，$lrl$表示此二叉树的左子树的右子树的左子树（的根）。那么时间复杂度$T(n)$有递推方程：$T(n)=T(l)+T(r)+O(1)\\=T(ll)+T(lr)+T(rl)+T(rr)+O(3)\\=...=O(叶子数)+O(分叉数)$而分叉数是$O(n)$，所以时间复杂度也是$O(n)$。

上述思路也可以用层序遍历来实现。

根据第二种定义，代码不太好写。不过不妨证明一下这两个定义是等价的。定义的等价性，等价于证明，对于$2^k$个数的逆序列$(n,n-1,...,1)$，$n=2^k$，依次进行$2^i,i=1,2,...,k-1$个翻转后（这里的意思是，先进行两个两个swap，再进行四个四个swap，这样一直下去），成为$(1,2,...,n)$。由数学归纳法，显然。