翻转一棵二叉树。
示例：
输入：
4
/
2 7
/ \ /
1 3 6 9
输出：
4
/
7 2
/ \ /
9 6 3 1
备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/invert-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
此题目考查二叉树反转，实际上是考察二叉树遍历，前序，中序，后序遍历都可以拿到节点，把节点的左右子树反转。
前序遍历代码如下：
1
2
3
4
5
6
7
8
9
10
11
|
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode tmp = root.right;
root.right = root.left;
root.left = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
|
层序遍历代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
Queue <TreeNode>queue = new LinkedList();
queue.add(root);
while (!queue.isEmpty()){
TreeNode node = queue.poll();
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
return root;
}
|