101. 对称二叉树

目录

一、问题描述

二、解题思路

三、代码

四、复杂度分析

---

一、问题描述

给你一个二叉树的根节点 root ， 检查它是否轴对称。

二、解题思路

我们可以使用递归来判断两棵子树是否镜像：

镜像的定义：

• 根节点值相同

• 左子树的左边 == 右子树的右边

• 左子树的右边 == 右子树的左边

三、代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/class Solution {
public:// 主函数bool isSymmetric(TreeNode* root) {if (!root) return true; // 空树是对称的return isMirror(root->left, root->right);}private:// 判断两棵树是否互为镜像bool isMirror(TreeNode* t1, TreeNode* t2) {if (!t1 && !t2) return true; // 两个空树是镜像的if (!t1 || !t2) return false; // 一个空一个非空，不对称if (t1->val != t2->val) return false; // 节点值不相等，不对称// 左对右，右对左进行递归比较return isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left);}
};

四、复杂度分析

• 时间复杂度：O(n)，n 是节点数，遍历了整棵树。

• 空间复杂度：O(h)，h 是树的高度，用于递归栈。