侧边栏壁纸
博主头像
Lin2J博主等级

升级了服务器,访问应该会更加流畅🇨🇳

  • 累计撰写 94 篇文章
  • 累计创建 39 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

27 二叉树的镜像

Lin2J
2021-07-21 / 0 评论 / 0 点赞 / 115 阅读 / 749 字 / 正在检测是否收录...

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

0

评论区