Is Symmetric

101. 对称二叉树

分析

主函数 isSymmetric
- 首先检查根节点是否为空。如果根节点为空，则树是对称的，返回 true
- 调用辅助函数 dfs，传入根节点的左右子树进行判断
辅助函数 dfs
- 判断当前两个节点：
  - 如果两者都为空，返回 true
  - 如果只有一个为空或节点值不同，返回 false
- 递归调用 dfs：
  - 比较左子树的左孩子和右子树的右孩子是否对称
  - 比较左子树的右孩子和右子树的左孩子是否对称

时间复杂度

时间复杂度 O(n)，n 为节点数，每个节点访问一次

空间复杂度

空间复杂度 O(h)，h 为树的高度，递归栈的深度

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution
{
public:
    bool isSymmetric(TreeNode* root)
    {
        // 如果根节点为空，直接返回 true
        if (!root) return true;

        // 调用辅助函数判断左右子树是否对称
        return dfs(root->left, root->right);
    }

    bool dfs(TreeNode* left, TreeNode* right)
    {
        // 如果两个子树都为空，说明对称
        if (!left && !right) return true;

        // 如果只有一个子树为空，或两子树值不等，不对称
        if (!left || !right || left->val != right->val) return false;

        // 递归检查：左子树的左孩子和右子树的右孩子是否对称
        // 以及左子树的右孩子和右子树的左孩子是否对称
        return dfs(left->left, right->right) && dfs(left->right, right->left);
    }
};