474，翻转二叉树的多种解决方式
Dream is not about what you want, but what you do after knowing who you are.
理想不是想想而已，是看清自我后的不顾一切。
问题描述
翻转一棵二叉树。
示例：
输入：
输出：
递归方式解决
翻转二叉树，可以先交换根节点的两个子节点，然后通过同样的方式在交换根节点的子节点的两个子节点……一直这样交换下去，画个图看一下
代码比较简单
1public TreeNode invertTree(TreeNode root) {
2 //递归的边界条件判断
3 if (root == null)
4 return null;
5 //先交换子节点
6 TreeNode left = root.left;
7 root.left = root.right;
8 root.right = left;
9 //递归调用
10 invertTree(root.left);
11 invertTree(root.right);
12 return root;
13}
BFS解决
如果对树的遍历比较熟悉的话，我们只要遍历树的所有节点，然后把他们的左右子节点相互交换即可，如果这样写，那么答案就比较多了。这里来看下二叉树的BFS解法，二叉树的BFS就是一层一层的遍历，像下面这样
二叉树的BFS代码如下
1public void levelOrder(TreeNode tree) {
2 if (tree == null)
3 return;
4 Queue<TreeNode> queue = new LinkedList<>();
5 queue.add(tree);//相当于把数据加入到队列尾部
6 while (!queue.isEmpty()) {
7 //poll方法相当于移除队列头部的元素
8 TreeNode node = queue.poll();
9 System.out.println(node.val);
10 if (node.left != null)
11 queue.add(node.left);
12 if (node.right != null)
13 queue.add(node.right);
14 }
15}
我们就参照这种方式来写下，每次遍历节点的时候都要交换子节点，所以代码很容易写
1public TreeNode invertTree(TreeNode root) {
2 if (root == null)
3 return root;
4 Queue<TreeNode> queue = new LinkedList<>();
5 queue.add(root);//相当于把数据加入到队列尾部
6 while (!queue.isEmpty()) {
7 //poll方法相当于移除队列头部的元素
8 TreeNode node = queue.poll();
9 //先交换子节点
10 TreeNode left = node.left;
11 node.left = node.right;
12 node.right = left;
13
14 if (node.left != null)
15 queue.add(node.left);
16 if (node.right != null)
17 queue.add(node.right);
18 }
19 return root;
20}
DFS解决
上面说了只要能遍历二叉树的所有节点，然后交换子节点，就能完成这道题，二叉树还有一种方式是DFS遍历，他的代码如下
1public static void treeDFS(TreeNode root) {
2 Stack<TreeNode> stack = new Stack<>();
3 stack.add(root);
4 while (!stack.empty()) {
5 TreeNode node = stack.pop();
6 System.out.println(node.val);
7 if (node.right != null) {
8 stack.push(node.right);
9 }
10 if (node.left != null) {
11 stack.push(node.left);
12 }
13 }
14}
我们来参照这种方式写下
1public TreeNode invertTree(TreeNode root) {
2 if (root == null)
3 return root;
4 Stack<TreeNode> stack = new Stack<>();
5 stack.add(root);
6 while (!stack.empty()) {
7 TreeNode node = stack.pop();
8 //先交换子节点
9 TreeNode left = node.left;
10 node.left = node.right;
11 node.right = left;
12 if (node.right != null) {
13 stack.push(node.right);
14 }
15 if (node.left != null) {
16 stack.push(node.left);
17 }
18 }
19 return root;
20}
总结
这道题其实很简单，基本上没什么难度，只要能遍历二叉树的所有节点都可以轻松完成。之前在中讲过二叉树的几种遍历方式，包括递归和非递归的。我们还可以使用二叉树的中序遍历来解决，二叉树的中序遍历代码如下
1public static void inOrderTraversal(TreeNode tree) {
2 Stack<TreeNode> stack = new Stack<>();
3 while (tree != null || !stack.isEmpty()) {
4 while (tree != null) {
5 stack.push(tree);
6 tree = tree.left;
7 }
8 if (!stack.isEmpty()) {
9 tree = stack.pop();
10 System.out.println(tree.val);
11 tree = tree.right;
12 }
13 }
14}
修改一下，就变成这题的答案了。
1public TreeNode invertTree(TreeNode root) {
2 if (root == null)
3 return root;
4 Stack<TreeNode> stack = new Stack<>();
5 TreeNode node = root;
6 while (node != null || !stack.isEmpty()) {
7 while (node != null) {
8 stack.push(node);
9 node = node.left;
10 }
11 if (!stack.isEmpty()) {
12 node = stack.pop();
13 //先交换子节点
14 TreeNode left = node.left;
15 node.left = node.right;
16 node.right = left;
17 //注意，这里是交换之后的，所以要修改
18 node = node.left;
19 }
20 }
21 return root;
22}
●
●
●
●
长按上图，识别图中二维码之后即可关注。
如果觉得有用就点个"赞"吧