226. 翻转二叉树
翻转一棵二叉树。
示例：
输入：
4
/
2 7
/ /
1 3 6 9
输出：
4
/
7 2
/ /
9 6 3 1
备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
// 先序遍历--从顶向下交换
// public TreeNode invertTree(TreeNode root) {
// if (root == null) return null;
// // 保存右子树
// TreeNode rightTree = root.right;
// // 交换左右子树的位置
// root.right = invertTree(root.left);
// root.left = invertTree(rightTree);
// return root;
// }
//中序遍历
// public TreeNode invertTree(TreeNode root) {
// if (root == null) return null;
// invertTree(root.left); // 递归找到左节点
// TreeNode rightNode= root.right; // 保存右节点
// root.right = root.left;
// root.left = rightNode;
// // 递归找到右节点 继续交换 : 因为此时左右节点已经交换了,所以此时的右节点为root.left
// invertTree(root.left);
// }
//后序遍历
// public TreeNode invertTree(TreeNode root) {
// // 后序遍历-- 从下向上交换
// if (root == null) return null;
// TreeNode leftNode = invertTree(root.left);
// TreeNode rightNode = invertTree(root.right);
// root.right = leftNode;
// root.left = rightNode;
// return root;
// }
//层次遍历
public TreeNode invertTree(TreeNode root) {
// 层次遍历--直接左右交换即可
if (root == null) return null;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
TreeNode node = queue.poll();
TreeNode rightTree = node.right;
node.right = node.left;
node.left = rightTree;
if (node.left != null){
queue.offer(node.left);
}
if (node.right != null){
queue.offer(node.right);
}
}
return root;
}
}