day143—递归—对称二叉树（LeetCode-101）

题目描述

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

示例 1：

输入：root = [1,2,2,3,4,4,3]输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]输出：false

提示：

• 树中节点数目在范围[1, 1000]内
• -100 <= Node.val <= 100

解决方案：

这段代码的核心功能是判断一棵二叉树是否为对称二叉树（即二叉树的左子树和右子树互为镜像），复用了 “判断两棵树是否相同” 的逻辑，将 “对称判断” 转化为 “左子树与右子树是否镜像相同”，采用递归实现，时间复杂度O(n)（n为节点数），空间复杂度O(h)（h为树的高度），是该问题的经典简洁解法。

核心逻辑

代码的核心思路是 “对称 = 左子树与右子树镜像相同”，通过复用isSameTree函数实现，关键是把 “镜像对比” 转化为 “两棵树的对比”：

1. 复用判断相同树的逻辑：isSameTree函数负责校验两棵树是否节点值、结构完全一致（前序递归，先校验当前节点，再递归校验左右子节点）；
2. 对称判断的转化：判断二叉树对称，等价于判断 “根节点的左子树” 和 “根节点的右子树” 是否满足 “镜像相同”—— 而isSameTree(root->left, root->right)恰好完成这个校验（因为isSameTree会逐节点对比root->left的左子节点与root->right的左子节点、root->left的右子节点与root->right的右子节点，这正是镜像对称的要求）；
3. 边界处理：若根节点为空，root->left和root->right均为空，isSameTree会返回true，符合 “空树是对称的” 逻辑。

总结

1. 核心思路：将 “对称二叉树判断” 转化为 “左子树和右子树是否相同” 的问题，复用已有逻辑，简化代码；
2. 关键等价性：对称二叉树的本质是「左子树与右子树镜像全等」，而isSameTree(root->left, root->right)恰好完成这种镜像校验；
3. 效率特点：与判断相同树的效率一致，每个节点仅遍历一次，时间O(n)，递归栈空间取决于树的高度，是最优解法之一。

函数源码：

/** * 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 isSameTree(TreeNode* p, TreeNode* q) { if(p==nullptr || q==nullptr){ return p==q; } return q->val==p->val && isSameTree(p->left,q->right) && isSameTree(p->right,q->left); } bool isSymmetric(TreeNode* root) { return isSameTree(root->left,root->right); } };