引言

大家好啊，我是前端拿破轮😁。

跟着卡哥学算法有一段时间了，通过代码随想录的学习，受益匪浅，首先向卡哥致敬🫡。

但是在学习过程中我也发现了一些问题，很多当时理解了并且AC的题目过一段时间就又忘记了，或者不能完美的写出来。根据费曼学习法，光有输入的知识掌握的是不够牢靠的，所以我决定按照代码随想录的顺序，输出自己的刷题总结和思考。同时，由于以前学习过程使用的是JavaScript,而在2025年的今天，TypeScript几乎成了必备项，所以本专题内容也将使用TypeScript，来巩固自己的TypeScript语言能力。

题目信息

翻转二叉树

leetcode题目链接

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

20250725103452

题目分析

本题考察判断一个二叉树是不是对称二叉树。所谓的对称二叉树，就是该二叉树在是沿着垂直方向的中间轴对称的。

本题同样也是递归实现的经典题目。但是就遇到了我们在上一篇文章 HomeBrew创始人都写不出来的翻转二叉树到底怎么做？中提到的问题，我们需要重新定义一个自己的递归函数，不能直接使用题目中提供的。

我们先来看一下leetcode官方提供的函数：

1
2
3
function isSymmetric(root: TreeNode | null): boolean {
    
};

我们来分析一下这个函数的签名，参数是一个根节点root（可能为null）。返回值是一个布尔值，表示以root为根节点的树是不是一棵对称二叉树。这个函数显然是不能用作递归函数的，原因是子问题和原始问题性质不同。什么意思呢？简单来说，我们的原始问题是判断一棵树是否是对称二叉树，但是我们的子问题应该是判断左右子树这两棵树是否镜像对称，而不是左右子树自身是否是对称二叉树。

直接说比较抽象。我们来看下面的图片：

20250725105432

按照题目要求，上面的二叉树很显然是一棵对称二叉树，但是我们来看左子树，根节点是2，左右孩子分别是3和4，很显然不是对称二叉树。也就是说原始问题和子问题之间没有联系。左右子树自身是不是对称二叉树和整棵树是不是对称二叉树两者之间根本没有关系。所以不能直接使用leetcode官方提供的函数来进行判读。

我们需要自己定义一个函数。我们用递归三部曲来进行一步一步的分析。

  1. 确定函数的参数和返回值以及其含义。

我们的函数可以命名为compare，这个函数接受两个参数，分别表示两棵子树的根节点root1和root2，返回值是一个布尔值，表示这两棵子树是否镜像对称。

这样定义函数，我们就发下父问题和子问题性质相同了，父问题是判断根节点的左右子树是否镜像对称，而子问题就是判断左子树的左子树和右子树的右子树是否镜像对称，以及左子树的右子树和右子树的左子树是否镜像对称。也就是外侧和外侧相比较，内侧和内侧相比较。比如上图中，左子树的左子树是3这个节点，右子树的右子树是3这个节点，两者都是外侧的，并且镜像对称。同理内侧的4也是，所以整棵树是对称的。

  1. 确定终止条件

这里的终止条件有多个：

  • 如果左右子树的根节点都为null，则左右子树一定镜像对称，直接返回true。
  • 如果左右子树的根节点一个为null，另一个不是null，则肯定不对称，直接返回false。
  • 如果左右子树节点的值不同，肯定不对称，直接返回fasle
  1. 确定单层递归逻辑

在单层逻辑中，需要返回我们说的外侧和外侧比，内侧和内侧比的结果。即递归调用compare函数，传入左子树的左子树和右子树的右子树。再调用传入左子树的右子树和右子树的左子树。然后将两者逻辑与的结果返回。因为要两者都满足才能说两棵子树镜像对称。

最后我们在leetcode给定的原始函数中，需要先判断边界条件进行剪枝，如果root为null，直接返回true；否则调用compare(root.left, root.right)并返回即可。

题解

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
26
27
28
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

const compare = (root1: TreeNode | null, root2: TreeNode | null): boolean => {
    // 确定终止条件
    if (!root1 && !root2) return true;
    if (!root1 || !root2) return false;
    if (root1.val !== root2.val) return false;

    return compare(root1.left, root2.right) && compare(root1.right, root2.left);
}

function isSymmetric(root: TreeNode | null): boolean {
    // 剪枝
    if (!root) return true;
    return compare(root.left, root.right);  
};

时间复杂度：$O(n)$，每个节点遍历一次

空间复杂度：$O(h)$，递归调用栈的深度,最好为$O(logn)$,最坏为$O(n)$.

总结

本题非常典型，需要自己定义新的递归函数，不能直接使用题目给定的。能否直接使用题目给定的函数的关键是子问题是否和原始问题具有相同的性质。在本题中子树是否对称对整棵树是否对称没有影响。所以不能直接调用。需要我们分析问题，定义新的递归函数。然后在主函数中调用我们自己定义的递归函数。

好了，这篇文章就到这里啦，如果对您有所帮助，欢迎点赞,收藏,分享👍👍👍。您的认可是我更新的最大动力。由于笔者水平有限，难免有疏漏不足之处，欢迎各位大佬评论区指正。

往期推荐✨✨✨

我是前端拿破轮，关注我，一起学习前端知识，我们下期见！