226. 翻转二叉树
1、概要
给你一棵二叉树的根节点
root，翻转这棵二叉树，并返回其根节点。
想要翻转它，其实就把每一个节点的左右孩子交换一下就可以
关键在于遍历顺序选择哪一种，遍历的过程中去翻转每一个节点的左右孩子就可以达到翻转效果。
中序不方便，会把某些节点的左右孩子翻转两次。（左孩子翻两次等于没翻，最终只相当于把父节点左右孩子换了，左右孩子的节点没换）想要纠正的话就不是中序了，在左 中 之后，依旧是左（因为右边还没交换的被挪到左了）
2、思路
递归法
- 递归函数的参数和返回值
传入节点指针，不需要其他参数，不需要返回值
void traverse(TreeNode root)
- 终止条件
当前节点为空的时候，就返回
if(root == null){
return;
}
- 单层递归
前序遍历，先交换root的左右孩子节点，然后反转左子树，反转右子树
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;//交换
traverse(root.left);
traverse(root.right);
迭代法
统一中序迭代反转
使用栈，放入顺序为 右 中 左，遇到中节点后面加个null
在读取到null时，进行pop，还有swap交换操作
层序遍历迭代反转
while里面，poll出节点后，每层swap交换操作即可
3、代码
class Solution {
public TreeNode invertTree(TreeNode root) {
//traverse(root);
//只要把每一个节点的左右孩子翻转一下的遍历方式都是可以的
//return order(root);
return inorder(root);
}
//统一中序迭代反转
public TreeNode inorder(TreeNode node){
//要处理的节点放入栈之后，紧接着放入一个空指针作为标记
if(node == null){
return node;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(node);
while(!stack.isEmpty()){
//右-中-左
TreeNode cur = stack.pop();
if(cur != null){
//右
if(cur.right!=null){
stack.push(cur.right);
}
stack.push(cur);
//中节点访问过，加空节点标记
stack.push(null);
//左
if(cur.left!=null){
stack.push(cur.left);
}
}else{//遇到空节点，才把下个节点放进结果集
cur = stack.peek();
stack.pop();
//可操做
swap(cur);
}
}
return node;
}
//层次迭代反转
public TreeNode order(TreeNode node){
if(node == null){
return null;
}
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(node);
//可操作
while(!que.isEmpty()){
int deep = que.size();
while(deep-- > 0){
TreeNode cur = que.poll();
//每个节点左右孩子反转
swap(cur);
if(cur.left!=null){
que.offer(cur.left);
}
if(cur.right!=null){
que.offer(cur.right);
}
}
//可操作
}
return node;
}
public void swap(TreeNode node){
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
}
void traverse(TreeNode root){
if(root == null){
return;
}
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
traverse(root.left);
traverse(root.right);
}
}