0101. Symmetric Tree ==================== 题目信息 -------- :题号: 0101. 对称二叉树 :难度: Easy :主题: 二叉树、递归、广度优先搜索、镜像结构 :原题: `LeetCode 0101 `_ :重点: 从逐个定位镜像位置,推导到直接维护镜像节点对,并用交叉孩子关系消除重复查找 题目重述 -------- 给定一棵二叉树的根节点 ``root``,判断整棵树是否关于穿过根节点的竖直中心轴镜像对称。 镜像对称同时约束结构和值。中心轴两侧的任意一对镜像位置必须满足:要么都没有节点,要么都存在节点且 节点值相等。若一对节点互为镜像,则左侧节点的左孩子对应右侧节点的右孩子,左侧节点的右孩子对应 右侧节点的左孩子。 树中节点总数在 ``1..1000`` 范围内,节点值在 ``-100..100`` 范围内。根节点非空;只要有一对镜像位置 出现“一空一非空”或节点值不同,就应返回 ``false``,否则返回 ``true``。判断过程不需要修改树。 自建示例 -------- * 交叉孩子对称:``root = [10,4,4,null,7,7,null]``,返回 ``true``。路径 ``LR`` 与 ``RL`` 上的两个 ``7`` 互为镜像; * 每层值相同但位置错误:``root = [10,4,4,2,null,2,null]``,返回 ``false``。路径 ``LL`` 上是 ``2``,其镜像位置 ``RR`` 却为空;另一个 ``2`` 位于 ``RL``,不能替代 ``RR``; * 镜像位置值不同:``root = [10,4,4,null,7,8,null]``,返回 ``false``。``LR`` 与 ``RL`` 都有节点, 但值分别为 ``7``、``8``; * 最小结构:``root = [1]``,返回 ``true``。根节点位于中心轴上,左右孩子形成 ``(null, null)``。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: bool mirrorRecursively(TreeNode* left, TreeNode* right) { if (!left || !right) { return left == right; } if (left->val != right->val) { return false; } return mirrorRecursively(left->left, right->right) && mirrorRecursively(left->right, right->left); } bool mirrorWithQueue(TreeNode* left, TreeNode* right) { std::queue> pending; pending.emplace(left, right); while (!pending.empty()) { const auto [first, second] = pending.front(); pending.pop(); if (!first || !second) { if (first != second) { return false; } continue; } if (first->val != second->val) { return false; } pending.emplace(first->left, second->right); pending.emplace(first->right, second->left); } return true; } public: bool isSymmetric(TreeNode* root) { return mirrorRecursively(root->left, root->right); } }; 题解 ---- 镜像比较对象 ~~~~~~~~~~~~ 二叉树中的位置可以用从根出发的方向路径唯一表示:``L`` 是根的左孩子,``LR`` 是先向左再向右到达的位置。 沿中心轴翻转时,每一步方向都会交换,因此一条路径的镜像位置由其中所有 ``L``、``R`` 互换得到: .. code-block:: text L <-> R LL <-> RR LR <-> RL 所以本题比较的对象不是“值相等的两个节点”,而是“路径互为镜像的两个位置”。值只能在位置已经对应后用于 检查,不能用来寻找镜像对象。树中可以有多个相同值,把左侧节点与右侧任意同值节点配对会失去结构信息。 第二个自建示例在最深一层都有两个值为 ``2`` 的节点,只比较每层的值或值出现次数会判为对称;实际路径 ``LL`` 的镜像是 ``RR``,``RL`` 上的另一个 ``2`` 并不在目标位置,结构仍然不对称。 同向比较也不成立。第一个自建示例本来对称,但若像“相同的树”那样比较左孩子与左孩子,就会把左侧 ``4`` 的 ``left`` 与右侧 ``4`` 的 ``left`` 配成 ``(null, 7)`` 并错误地返回假。镜像关系必须比较 ``LR`` 与 ``RL``,也就是交叉方向的孩子。 从位置查找到节点对 ~~~~~~~~~~~~~~~~~~~~ 一个直接且正确的做法是记录每个非空节点及其两个孩子位置的路径:对每条路径生成交换 ``L``、``R`` 后的 镜像路径,再从根出发找到两端位置,比较它们是否同时为空或值相等。非空节点覆盖值检查,孩子位置覆盖首次 出现的结构分叉;路径映射又是唯一的,因此检查完这些有限位置不会遗漏结构差异或值差异。 这个做法保存了超出需要的信息。不同节点的路径通常共享很长的前缀,却要为每个位置重新从根查找;高度为 ``h`` 的树中,所有查找最多会重复走过 ``O(nh)`` 段路径。真正有用的不是完整路径,而是当前已经到达的 一对镜像节点。 二叉树的父子结构给出了压缩路径的方法。若 ``left``、``right`` 已经是一对镜像节点,下一层对应关系只有 两组: .. code-block:: text 外侧:left.left <-> right.right 内侧:left.right <-> right.left 父节点对已经包含共同路径前缀,沿交叉方向各走一步就能得到孩子对,不必回到根重新定位。这样,逐个保存和 查询完整路径的工作被压缩为沿树传递一个节点对,每个非空节点至多进入一次比较。 直接状态定义 ~~~~~~~~~~~~ 定义 ``mirror(left, right)`` 表示以 ``left``、``right`` 为根的两棵子树是否互为镜像。状态面对的不是 单个节点,而是一对已经确定位置关系的节点,因此只需处理三种互斥情况: #. 两者都为空:两个镜像位置的结构一致,当前状态返回 ``true``; #. 只有一者为空:两个位置的结构不同,当前状态返回 ``false``; #. 两者都非空:当前值必须相等,并且外侧孩子对、内侧孩子对都必须互为镜像。 .. code-block:: text mirror(left, right) = left.value == right.value AND mirror(left.left, right.right) AND mirror(left.right, right.left) 这一定义覆盖了所有失败来源。结构差异第一次出现时会形成“一空一非空”的节点对,值差异会在对应的非空 节点对上暴露;当前节点相同后,余下位置又被唯一划分为两组互不重叠的交叉子树对。 递归主解 ~~~~~~~~ ``mirrorRecursively`` 直接执行上述状态定义。空指针检查必须在读取节点值之前,并通过 ``left == right`` 同时合并“双空成功”和“一空失败”:进入该分支时,两个指针相等只可能是都为 ``nullptr``。 两个节点都存在后,先检查当前值。值不同便立即返回,不再生成无意义的孩子状态;值相同才递归处理 ``(left->left, right->right)`` 和 ``(left->right, right->left)``。逻辑与的短路顺序表示外侧状态失败时, 内侧状态不再访问,但交换两组状态的先后不会改变结果。 根节点位于对称轴上,只会与自己对应,无需加入状态。``isSymmetric`` 直接以 ``root->left``、 ``root->right`` 建立第一对镜像节点。公开入口选择递归法,因为状态定义、递归分支和树的结构完全对应, 无需额外维护容器。 显式队列替代 ~~~~~~~~~~~~ 递归调用栈隐式保存“父节点已匹配、自身尚未检查”的节点对。``mirrorWithQueue`` 把同一状态改存到 ``pending`` 队列中;循环开始时,队列中的每一项都保持这个含义。 弹出节点对后的检查顺序与递归版相同:先处理空指针,再比较非空节点值,只有当前节点对匹配时才把两组 交叉孩子加入队尾。若在检查当前状态前就加入孩子,代码既可能解引用空指针,也会制造父节点已经失败却仍被 处理的无效状态。 队列没有发现新的判断条件,只是把调用栈替换为显式的待处理集合,并按层推进。它避免依赖递归深度,代价是 宽树上可能同时保存较多节点对;递归法则只保存当前深度上的未完成调用。因此队列作为栈深受限场景的替代, 不取代本题更直接的递归主解。 待处理状态走读 ~~~~~~~~~~~~~~ 用 ``L``、``R`` 路径标记节点位置。对 ``[10,4,4,null,7,7,null]`` 执行队列方案时,状态依次变化如下: .. list-table:: :header-rows: 1 * - 步骤 - 取出的节点对 - 当前检查 - 检查后的 ``pending`` * - 0 - 无 - 放入根的左右孩子 - ``[(L:4, R:4)]`` * - 1 - ``(L:4, R:4)`` - 值相等,加入两组交叉孩子 - ``[(LL:null, RR:null), (LR:7, RL:7)]`` * - 2 - ``(LL:null, RR:null)`` - 两侧都空,结构匹配 - ``[(LR:7, RL:7)]`` * - 3 - ``(LR:7, RL:7)`` - 值相等,加入两组空孩子 - ``[(LRL:null, RLR:null), (LRR:null, RLL:null)]`` * - 4 - ``(LRL:null, RLR:null)`` - 两侧都空,结构匹配 - ``[(LRR:null, RLL:null)]`` * - 5 - ``(LRR:null, RLL:null)`` - 两侧都空,结构匹配 - ``[]`` 队列耗尽表示每一对镜像位置都通过。递归法处理的是同一批节点对,只是会先沿第一组孩子状态深入,再回来 处理第二组。 对反例 ``[10,4,4,2,null,2,null]``,第一对 ``(L:4, R:4)`` 通过后会生成 ``(LL:2, RR:null)`` 与 ``(LR:null, RL:2)``。队列弹出第一项就命中“一空一非空”并返回 ``false``, 第二项无需处理;递归法也会因逻辑与短路停在同一处。两个值 ``2`` 是否都存在并不重要,失败由第一个错误的 镜像位置决定。 最小结构 ``[1]`` 的初始状态就是 ``(L:null, R:null)``。空指针分支直接返回 ``true``,既不会读取节点值, 也不会继续生成孩子状态。 复杂度与主解选择 ~~~~~~~~~~~~~~~~ 设树有 ``n`` 个非空节点、高度为 ``h``、最大层宽为 ``w``。递归和队列都让每个非空节点只进入一个镜像 节点对,空孩子状态数量也与节点数同阶,因此最坏时间都是 ``O(n)``;发现首个结构或值差异时会提前结束。 递归法的工作空间来自调用栈,最坏为 ``O(h)``。队列最多保存同一层的节点对以及由它们产生的下一层状态, 工作空间为 ``O(w)``,最坏可达 ``O(n)``。两种方法都不修改输入,返回值之外没有结果空间;公开入口采用 递归法,原因是它以最少状态直接表达镜像定义,而不是因为队列在正确性或时间复杂度上较弱。