📃 题目描述

题目链接：

• 剑指 Offer 27. 二叉树的镜像 (opens new window)
• 226. 翻转二叉树 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

翻转一棵二叉树。

示例：

输入：
     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：
     4
   /   \
  7     2
 / \   / \
9   6 3   1

🔔 解题思路

所谓翻转，就是把每个节点的左右孩子交换一下就行了。

所以思路很简单，在遍历二叉树的过程中，去翻转每一个节点的左右孩子就可以达到整体翻转的效果。

总共四种遍历方式，除了中序遍历（中序遍历会把某些节点的左右孩子翻转了两次），其余三种方式都是可以的

以先序遍历为例：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        
        if (root.left == null && root.right == null) {
            return root;
        }
        
        // 先翻转根节点的左右孩子
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        // 再翻转左孩子的左右孩子
        invertTree(root.left);
        // 再翻转右孩子的左右孩子
        invertTree(root.right);
        
        return root;
    }
}

再来波先序遍历的迭代法：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        
        if (root.left == null && root.right == null) {
            return root;
        }
        
        // 辅助栈
        Stack<TreeNode> stack = new Stack<>();
        // 工作指针
        TreeNode cur = root;

        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.push(cur);
                
                // 交换该节点的左右孩子
                TreeNode temp = cur.left;
                cur.left = cur.right;
                cur.right = temp;

                cur = cur.left;
            } else {
                cur = stack.pop();
                cur = cur.right;
            }
        }
        
        return root;
    }
}

是不是很简单，其实就是把先序遍历中，将某个节点加入结果集 res 的那行代码，修改成了交换该节点的左右孩子

💥 复杂度分析

• 空间复杂度：O(LogN)
• 时间复杂度：O(N), 我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树