对称二叉树 | 秋招知识库

题目链接 · 灵神原题解（署名来源）

视频讲解

看完这两期视频，对递归的理解更上一层楼！

【基础算法精讲 09】

【基础算法精讲 10】

思路

把输入的二叉树拆分成左子树 $p$ 和右子树 $q$ 。我们需要判断 $p$ 和 $q$ 是否互为镜像。

类似 100. 相同的树，必须满足：

$p . val$ 等于 $q . val$ 。
$p$ 的左儿子与 $q$ 的右儿子互为镜像。这是一个和原问题相似的子问题，可以递归判断。
$p$ 的右儿子与 $q$ 的左儿子互为镜像。这是一个和原问题相似的子问题，可以递归判断。

Python 解法1C++ 解法1

python

class Solution:
    # 100. 相同的树（改成镜像判断）
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None:
            return p is q
        return p.val == q.val and self.isSameTree(p.left, q.right) and self.isSameTree(p.right, q.left)

    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.isSameTree(root.left, root.right)

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
    // 100. 相同的树（改成镜像判断）
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr || q == nullptr) {
            return p == q;
        }
        return p->val == q->val && isSameTree(p->left, q->right) && isSameTree(p->right, q->left);
    }

public:
    bool isSymmetric(TreeNode* root) {
        return isSameTree(root->left, root->right);
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 为二叉树的节点个数。
空间复杂度： $O (n)$ 。最坏情况下，二叉树退化成一条链，递归需要 $O (n)$ 的栈空间。

思考题

这棵二叉树，有多少棵子树是对称二叉树？最大的对称二叉子树有多少个节点？
分析暴力做法的时间复杂度。
你能做到 $O (n)$ 吗？

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

视频讲解 ​

思路 ​

复杂度分析 ​

思考题 ​

分类题单 ​

视频讲解

思路

复杂度分析

思考题

分类题单