28 对称的二叉树

剑指 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)$ 大小的递归栈。