【Leetcode】226. Invert Binary Tree

题目地址：

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)$。由数学归纳法，显然。