XingHuiSamaの宝藏之地

给你一个二叉树的根节点 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

‍

之前Java是用迭代的思路做的，这次想不到了。

‍
‍

1. 算法核心思想：照镜子与树的序列化

判断一棵二叉树是否对称，本质上是判断它的左子树和右子树是否互为镜像。

为了解决这个问题，采用了“序列化比对”的策略：

定制遍历规则：针对左子树，采用标准的前序遍历（根 -> 左 -> 右）；针对右子树，采用“镜像”的前序遍历（根 -> 右 -> 左）。
记录结构（序列化）：在遍历过程中，将途径的节点值存入数组中。为了防止不同结构的树产生相同的序列（例如 [2, 左2] 和 [2, 右2]），我们必须将空节点（NULL）也记录下来。由于题目限制节点值在 [-100, 100] 之间，我们可以安全地用 -101 来代表空节点。
比对结果：如果这两棵子树互为镜像，那么它们按照上述相反方向遍历出来的数组，必须是一模一样的。

‍

2. 代码逻辑拆解

主控函数 isSymmetric：
- 首先处理特殊情况，如果整棵树为空，那它天然是对称的，返回 true。
- 声明两个数组 pre1 和 pre2，分别用来接收左半边和右半边的遍历结果。
- 调用两个方向相反的遍历函数。
- 遍历结束后，先比较数组长度，长度不等直接判 false；再逐个元素比较，任何一个位置的值不同都说明不对称。如果全部相同，则返回 true。
左侧探测器 func1（标准前序）：
- 采用 根 -> 左 -> 右 的顺序。
- 遇到空节点时，在数组里记下 -101 并立即 return（防止发生段错误）。
- 非空时，先记录当前根节点的值，然后向左深挖，最后向右深挖。
右侧探测器 func2（镜像前序）：
- 采用 根 -> 右 -> 左 的顺序（这就是“照镜子”的核心动作）。
- 同样遇到空节点记录 -101 并返回。
- 先记录根节点的值，然后一定要先向右深挖，再向左深挖。

‍

class 对称二叉树 {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) {
            return true;
        }
        vector<int> pre1;
        vector<int> pre2;

        func1(pre1,root->left);
        func2(pre2,root->right);

        if (pre1.size() != pre2.size()) {
            return false;
        }

        for (int i = 0; i < pre1.size(); i++) {
            if (pre1[i] != pre2[i]) {
                return false;
            }
        }

        return true;

    }
    void func1(vector<int>& pre, TreeNode* node) {
        if (node == NULL) {
            pre.push_back(-101);
            return;
        }

        pre.push_back(node->val);

        func1(pre, node->left);

        func1(pre, node->right);
    }

    void func2(vector<int>& pre, TreeNode* node) {
        if (node == NULL) {
            pre.push_back(-101);
            return;
        }

        pre.push_back(node->val);

        func2(pre, node->right);

        func2(pre, node->left);
    }
};

‍

3. 复杂度分析

时间复杂度：O(N)。其中 N 为二叉树的节点数。遍历左子树和右子树会访问所有的节点一次（耗时 O(N)），最后比较两个长度为 N 的数组也会花费 O(N) 的时间。总体时间复杂度为线性的 O(N)。
空间复杂度：O(N)。主要开销来源于两个部分：
1. 数组开销：我们开辟了 pre1 和 pre2 两个数组来存储节点值，最坏情况下需要存储 N 个节点以及相应的空节点标记。
2. 栈开销：递归调用会占用系统栈空间，最坏情况下（树退化为链表）栈的深度为 O(N)。 两者加起来，总的空间复杂度仍为 O*(N)。*

‍