「力扣」第 226 题：反转一棵二叉树

• 题目链接：226. 翻转二叉树 (opens new window)；
• 题解链接：前、中、后序遍历、层序遍历 (opens new window)。

和二叉树相关的问题，在面试中是非常常见的。一旦我们熟悉了这些问题以后，会发现这些问题其实是非常简单的。

题目描述

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Example 2:

Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

Input: root = []
Output: []

备注: 这个问题是受到 Max Howell (opens new window)的 原问题 (opens new window) 启发的 ：

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

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

思路分析

算法是非常重要的基本功。即使是大公司都非常注重基础问题的考察。

这道问题可以说是一个经典的问题。LeetCode 上有如下备注：

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

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

思路 1：我们可以使用递归方法来完成，我们写好之后，会发现其实就是完成了一次深度优先遍历，并且是前序遍历，有的朋友可能写出来的后序遍历，那么我们不禁要问，中序遍历可不可以，答案是不可以，因为中序遍历很可能一个结点会被翻转两次，这与我们的要求是违背的。

Java 代码：

Java 代码：后序遍历

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        invertTree(root.left);
        invertTree(root.right);
        // swap root.left 和  root.right
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }
}

Java 代码：与上面的代码等价

public class Solution2 {

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        root.left = invertTree(right);
        root.right = invertTree(left);
        return root;
    }
}

方法一：前序遍历

Java 代码：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        // 左子树和右子树交换，即使左右子树都空也不影响正确性
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        // 递归翻转左右子树
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

方法二：中序遍历

注意：写中序遍历的时候，不能仅仅只是将前序遍历的代码顺序调整一下。

因为在“中序遍历”的时候，左右子树已经交换过了，因此原来写 invertTree(root.right); 的地方，应该写作 invertTree(root.left);。

Java 代码：

public class Solution {

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        invertTree(root.left);

        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        // 注意：因为左右子树已经交换了，因此这里不能写 invertTree(root.right);
        invertTree(root.left);
        return root;
    }
}

方法三：后序遍历

Java 代码：

public class Solution {

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        invertTree(root.left);
        invertTree(root.right);

        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }
}

方法四：层序遍历

Java 代码：

import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    public TreeNode invertTree(TreeNode root) {
        // 结点为空的特殊情况要先考虑
        if (root == null) {
            return null;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode curNode = queue.poll();
            // 只要其中之一非空，我都交换，并且把非空的结点添加到队列里
            if (curNode.left != null || curNode.right != null) {
                // 先翻转
                TreeNode temp = curNode.left;
                curNode.left = curNode.right;
                curNode.right = temp;
                // 把非空的节点加入队列
                if (curNode.left != null) {
                    queue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    queue.offer(curNode.right);
                }
            }
        }
        return root;
    }
}

---

作者：liweiwei1419 链接：https://suanfa8.com/tree/solutions/0226-invert-binary-tree 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。