27 二叉树的镜像

Lin2J
2021-07-21 / 0 评论 / 86 阅读
温馨提示:
本文最后更新于2021-07-21,若内容或图片失效,请留言反馈。

剑指 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)$ 大小。