474，翻转二叉树的多种解决方式

Original 山大王wld 数据结构和算法 2022-05-01

收录于合集 #算法图文分析 161个

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}

总结

这道题其实很简单，基本上没什么难度，只要能遍历二叉树的所有节点都可以轻松完成。之前在373，数据结构-6,树中讲过二叉树的几种遍历方式，包括递归和非递归的。我们还可以使用二叉树的中序遍历来解决，二叉树的中序遍历代码如下

 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}