226.翻转二叉树

翻转一棵二叉树。

示例：

输入：

4

/ \

2 7

/ \ / \

1 3 6 9

输出：

4

/ \

7 2

/ \ / \

9 6 3 1

备注: 这个问题是受到 Max Howell 的 原问题 启发的 ：

谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

思路

• 本质：交换所有节点的左右子树

• 保证遍历到所有节点：四种遍历方式皆可

  • 前序遍历
  • 中序遍历
  • 后序遍历
  • 层序遍历

代码

节点类

public class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) {

val = x;

}

}

前序遍历，交换左右子树

// 前序遍历

private TreeNode invertTree(TreeNode root) {

if (root == null) return null;

// 前序交换

TreeNode tempNode = new TreeNode(0);

tempNode = root.left;

root.left = root.right;

root.right = tempNode;

invertTree(root.left);

invertTree(root.right);

return root;

}

后序遍历

// 后序遍历

private TreeNode invertTree(TreeNode root) {

if (root == null) return null;

invertTree(root.left);

invertTree(root.right);

// 后序交换

TreeNode tempNode = new TreeNode(0);

tempNode = root.left;

root.left = root.right;

root.right = tempNode;

return root;

}

中序遍历

注意：由于在中序遍历中，交换了左右节点，导致最后递归访问右节点时，写为左节点，因为实际上右节点已经被置换到了左节点的位置上

中序遍历

// 中序遍历

private TreeNode invertTree(TreeNode root) {

if (root == null) return null;

invertTree(root.left);

// 中序交换

TreeNode tempNode = new TreeNode(0);

tempNode = root.left;

root.left = root.right;

root.right = tempNode;

invertTree(root.left); // 此处实际的右节点，已经被交换到了左节点的位置上

return root;

}

层序遍历

// 层序遍历

private TreeNode invertTree(TreeNode root) {

if (root == null) return null;

// 层序交换

// 维护一个队列

Queue<TreeNode> queue = new LinkedList<>();

// 根节点入队

queue.offer(root);

while (!queue.isEmpty()) {

// 队头A出队，访问

TreeNode head = queue.poll();

TreeNode tempNode = head.left;

head.left = head.right;

head.right = tempNode;

// 左右入队

if (head.left != null) queue.offer(head.left);

if (head.right != null) queue.offer(head.right);

}

return root;

}