28 对称的二叉树

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

剑指 Offer 28. 对称的二叉树

请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。

解题思路:

判断一棵树是否对称,实际上应该判断树的 左节点 和 右节点 是否互为镜像。

然后判断两颗树 $p$, $q$ 是否互为镜像,首先需要判断各自根节点的值是否相等,然后再递归比较 $p$ 的左子树是否和 $q$ 的右子树互为镜像,并且 $p$ 的右子树也要和 $q$ 的左子树互为镜像。(互为镜像的意思其实就是对称)

递归函数

终止条件

  1. 如果 $p$ 和 $q$ 同时为 $null$,返回 $true$ 。
  2. 如果 $p$ 或者 $q$ 只有一个为 $null$ ,返回 $false$。
  3. 如果 $p.val \neq q.val$ ,返回 $false$。

递归工作

  1. 判断 $p.left$ 和 $q.right$ 是否互为镜像。
  2. 判断 $p.right$ 和 $q.left$ 是否互为镜像。

代码:

public boolean isSymmetric(TreeNode root) {
    if(root == null) {
        return true;
    }
    return isSymmetric(root.left, root.right);
}

private boolean isSymmetric(TreeNode p, TreeNode q) {
    if(p == null && q == null) {
        return true;
    }
    if(p == null || q == null) {
        return false;
    }
    if(p.val != q.val) {
        return false;
    }
    return isSymmetric(p.left, q.right) && isSymmetric(p.right, q.left);
}

复杂度分析

  • 时间复杂度$O(N)$:$N$ 为树的节点数量,判断对称需要遍历树的所有节点,一次递归判断 $2$ 个节点是否对称,因此最多调用 $N/2$ 次递归函数。

  • 空间复杂度$O(N)$:最差情况下,树退化成链表,系统使用 $O(N)$ 大小的递归栈。

树退化为链表