27 二叉树的镜像

剑指 Offer 27. 二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

解题思路：

要求一棵树的镜像，其实就是将树的的左右子节点交换一下，类似于交换数组中两个位置的元素。

递归函数

终止条件：当 $root$ 为 $null$ 时，返回 $null$；

递推工作：

1. 使用 $tmp$ 变量保存 $root.left$。
2. 把 $root$.left 指向 右节点 的递归结果 $mirrorTree(root.right)$。
3. 把 $root.right$ 指向原先保存的 左子树 的递归结果 $mirrorTree(tmp)$。
4. 返回 root。

代码：

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

复杂度分析

• 时间复杂度$O(N)$ ：其中 $N$ 为树的节点数量，交换工作需要遍历所有节点。

• 空间复杂度$O(N)$：最差情况下，树退化成链表，递归栈的占用 $O(N)$ 大小。