翻转等价二叉树

记住「值相同后,孩子有不翻、翻两种配法,或关系任一成立即可」,下面逐帧套它。

翻转等价二叉树 · T1(左) ↔ T2(右)：先看清两棵树:左边是 T1、右边是 T2。它们的节点值是同一批(50、30、80、20、40),只是挂的位置不同。我们从两个根开始,同步往下比。

翻转等价二叉树 · T1(左) ↔ T2(右)：先单看 T1 的形状:根是 50,左边挂 30、30 下面又有 20 和 40,右边是叶子 80。

翻转等价二叉树 · T1(左) ↔ T2(右)：再单看 T2:根也是 50,但左边是叶子 80、右边挂 30、30 下面是 40 和 20。和 T1 比,像是某些节点的左右被对调了,这正是翻转。

翻转等价二叉树 · T1(左) ↔ T2(右)：从根开始:T1 的根是 50,T2 的根也是 50。先看这一对的值。

翻转等价二叉树 · T1(左) ↔ T2(右)：50 和 50 相等,根这一层对上了。接下来要让它们的孩子也对上。

翻转等价二叉树 · T1(左) ↔ T2(右)：孩子有两种配法:「不翻」让 T1 左30 配 T2 左80、T1 右80 配 T2 右30;「翻」让 T1 左30 配 T2 右30、T1 右80 配 T2 左80。两种里只要有一种能让孩子全对上就行,先试不翻。

翻转等价二叉树 · T1(左) ↔ T2(右)：先试不翻:让 T1 的左孩子配 T2 的左孩子,也就是 30 配 80。看这一对。

翻转等价二叉树 · T1(左) ↔ T2(右)：30 和 80 不相等。不翻这种配法,头一对就对不上,所以「不翻」这条路走不通。那就改试「翻」。

翻转等价二叉树 · T1(左) ↔ T2(右)：改试翻:把 T1 的左配 T2 的右、T1 的右配 T2 的左。先看 T1 左孩子 30 配 T2 右孩子 30。

翻转等价二叉树 · T1(左) ↔ T2(右)：30 和 30 相等!这一对值对上了,但它们各自还有孩子,得递归进这两个 30 的子树继续比。

翻转等价二叉树 · T1(左) ↔ T2(右)：进到两个 30 的子树。先试不翻:T1 这个 30 的左孩子 20,配 T2 那个 30 的左孩子 40。

翻转等价二叉树 · T1(左) ↔ T2(右)：20 和 40 不相等,这层不翻又失败。再试翻:把 20 配到 T2 那个 30 的右孩子去。

翻转等价二叉树 · T1(左) ↔ T2(右)：翻转配法:T1 的 20 配 T2 那个 30 的右孩子 20。看这一对。

翻转等价二叉树 · T1(左) ↔ T2(右)：20 配 20,两个都是叶子、没有孩子,直接相等(都空的子树也相等)。这一对 ✓。

翻转等价二叉树 · T1(左) ↔ T2(右)：再看翻转配法的另一对:T1 的 40 配 T2 那个 30 的左孩子 40。

翻转等价二叉树 · T1(左) ↔ T2(右)：40 配 40,也是两个叶子,相等 ✓。两个孩子都对上了。

翻转等价二叉树 · T1(左) ↔ T2(右)：小结这棵 30 子树:在 30 这个节点处翻一下,20 配 20、40 配 40,整棵子树就对上了。所以「30 ↔ 30」这一对返回真。

翻转等价二叉树 · T1(左) ↔ T2(右)：回到根的翻转配法,还剩另一半:T1 的右孩子 80,配 T2 的左孩子 80。

翻转等价二叉树 · T1(左) ↔ T2(右)：80 配 80,两个叶子,相等 ✓。至此根的翻转配法两半都成立。

翻转等价二叉树 · T1(左) ↔ T2(右)：把翻过的地方圈出来:整个过程只在根 50 和左边那个 30 处各翻了一次(交换左右孩子),其它节点都保持原样。这两翻就能让 T1 变成 T2。

翻转等价二叉树 · T1(左) ↔ T2(右)：根这一层用翻转配法走通了:50 对 50,翻转后 30 配 30、80 配 80,而 30 子树里又翻了一次让 20、40 对上。整棵树在 50 和 30 处各翻一次就相等,所以返回 true。回头看,我们没真去搬动任何节点,只是每对节点试「不翻 或 翻」两种配法,一遍递归就判完。

边界:都空真、一空一非空假、单节点只看值。

两个追问:值不同即短路所以是线性;可用「节点对」栈改迭代。