从零开始写算法——二叉树篇3:对称二叉树 + 二叉树直径-平芜编程栈

二叉树是数据结构中递归思想的最佳演练场。很多同学在刷题时，往往看答案觉得很简单，自己写却无从下手。

其实，二叉树的递归无非就两种套路：

怎么传下去？（父节点把要求传给子节点，如判断对称）
怎么收上来？（子节点把结果汇报给父节点，如计算直径）

今天我们通过两道经典题目（LeetCode 101 和 543），来彻底搞懂这两个套路。

01. 对称二叉树 (Symmetric Tree)

题目解析

我们要判断一棵树是不是轴对称的。这就好比我们在树的中间放一面镜子，左边的样子和右边的样子必须完全重合。

核心逻辑：镜像对比

很多初学者容易犯的错误是：直接判断root->left和root->right是不是“完全相同”的树。错！对称不是“相同”，而是“镜像”。

我们可以把这棵大树拆解成无数个小的“三角单元”。对于任意两个对称位置的节点p（左边那个）和q（右边那个），如果要满足对称，必须同时满足三个条件：

值相等：p的值必须等于q的值。
外侧对齐：p的左孩子（最外侧）必须等于q的右孩子（最外侧）。
内侧对齐：p的右孩子（靠近中间）必须等于q的左孩子（靠近中间）。

代码深度拆解

C++代码实现：

class Solution { public: bool isSymmetric(TreeNode* root) { // 根节点的左子树和右子树进行镜像对比 return isSameTree(root->left, root->right); } // 这里虽然函数名叫 isSameTree，但实际逻辑是 checkMirror // 作用：判断 p 和 q 两棵树是否互为镜像 bool isSameTree(TreeNode* p, TreeNode* q) { // 1. 递归终止条件：处理空节点的情况 // 如果两个都为空，说明到底了且匹配，返回 true // 如果只有一个为空，说明不对称（结构不同），返回 false if (p == nullptr || q == nullptr) return q == p; // 2. 核心递归逻辑 // 条件A: 当前节点值必须一样 // 条件B: p的左边 VS q的右边 (外侧互相对比) // 条件C: p的右边 VS q的左边 (内侧互相对比) return p->val == q->val && isSameTree(p->left, q->right) && isSameTree(p->right, q->left); } };

为什么这么写？代码中最精髓的一句是isSameTree(p->left, q->right) && isSameTree(p->right, q->left)。这正是体现了**“镜像”**的定义。如果你写成了p->left, q->left，那就是判断两棵树是否完全一样（平移），而不是对称了。

复杂度分析

时间复杂度：O(N)。我们需要遍历树中的每一个节点一次。
空间复杂度：O(H)，其中 H 是树的高度。这里的空间消耗主要来自递归调用的栈空间。在最坏情况下（树退化成链表），高度为 N；最好情况下（完全二叉树），高度为 logN。

02. 二叉树的直径 (Diameter of Binary Tree)

题目解析

这道题要求的是二叉树中任意两个节点间的最长路径长度。注意一个大坑：这条最长路径不一定经过根节点。它可能完全存在于左子树内部，也可能在右子树内部。

核心逻辑：后序遍历 + 全局打擂台

既然路径可能出现在任何地方，但所有的路径都有一个共同点：它一定有一个“最高点”（转折点）。对于任何一个节点，穿过该节点的最长路径 =左子树的最大深度+右子树的数据深度。

所以我们的策略是：

自底向上（后序遍历）：先算出子树的深度，再汇报给父节点。
全局打擂：在计算深度的过程中，顺便计算“经过当前节点的最长路径”，并用一个全局变量ans记录历史最大值。

代码深度拆解

C++代码实现：

class Solution { // 全局变量维护最大直径 // 因为最长路径可能不经过根节点，所以需要在遍历过程中实时更新最大值 int ans = 0; // 这个函数的定义非常关键： // 它的作用是：返回以 root 为根的树的【最大深度】 // 它的副作用是：更新经过 root 的【最大直径】 int dfs(TreeNode* root) { // 1. 终止条件：空节点深度为 0 if (root == nullptr) return 0; // 2. 递归获取左右子树的深度（自底向上） int left = dfs(root->left); int right = dfs(root->right); // 3. 【核心逻辑之一：更新答案】 // 经过当前节点的最长路径 = 左臂长 + 右臂长 // 这是一条"穿过"当前节点的路径，类似倒"V"字型 ans = max(ans, left + right); // 4. 【核心逻辑之二：返回深度】 // 当前节点要汇报给父节点的是：我这条分支有多长？ // 我只能选左边或右边更长的一条路继续往上延伸，不能两条都选（那样就分叉了） // 所以返回 max(left, right) + 1 (加1是加上当前节点自己) return max(left, right) + 1; } public: int diameterOfBinaryTree(TreeNode* root) { dfs(root); return ans; } };

为什么这么写？很多同学搞混淆的地方在于：为什么更新ans用加法，而返回值用max？

更新ans：我们在找直径（路径长度）。一条路径穿过当前节点，是把左腿和右腿连起来，所以是left + right。
返回值：我们在算深度（高度）。对于父节点来说，当前节点只是它的一条“腿”。一条路径不能分叉，只能选最长的那条腿往上走，所以是max(left, right) + 1。