这个题反正天天被用来开玩笑嘲讽人。 说什么你天天开发大project，缺连个invery binary tree都不会。 所以这个题是码农为了尊严背也要背下来的。
其实很简单，唯一要注意的就是如果你root.left = invertTree(root.right) 这个时候root.left已经改变了 你再做root.right=invertTree(root.left)就不对了。因为left已经改变了
public class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null)
return null;
TreeNode leftsub = invertTree(root.right);
TreeNode rightsub = invertTree(root.left);
root.left = leftsub;
root.right = rightsub;
return root;
}
}
不过！ 我觉得我要是面试官，我不会这么简单让interviewer过，我会升级难度让做一个iterative version 的invert binary tree!
如果说invert binary tree using recursion是EASY level, iterative version可以算MEDIUM 难度了。假设我们忘记recursion,忘记代码，就想象出这颗Tree的样子。 我们怎么iteratively invert呢？
很自然的，第一步是把root的left,right subtree交换一下对不对？ 然后第一步结束。 第二步，要把root.left subtree的root的left,right subtree交换一下， 把root.right subtree的root的left,right subtree交换一下。 so on... 这个pattern怎么看起来有点像BFS??? 这个时候就可以尝试一下用BFS来做了。 BFS的常规做法用什么？ 恩， Queue. 所以我们可以用queue, level by level 的push/pop nodes。
