翻转等价二叉树 图解题解

这道题到底在问什么

输入

T1 根50(左30〔20,40〕,右80) / T2 根50(左80,右30〔40,20〕)

输出

true(在 50 和 30 处各翻一次)

输入

T1=[50,30,80] / T2=[50,30,90]

输出

false(值对不上)

最优解：一步一步想明白

1. 3记住「值相同后,孩子有不翻、翻两种配法,或关系任一成立即可」,下面逐帧套它。
2. 4先看清两棵树:左边是 T1、右边是 T2。它们的节点值是同一批(50、30、80、20、40),只是挂的位置不同。我们从两个根开始,同步往下比。
3. 5先单看 T1 的形状:根是 50,左边挂 30、30 下面又有 20 和 40,右边是叶子 80。
4. 6再单看 T2:根也是 50,但左边是叶子 80、右边挂 30、30 下面是 40 和 20。和 T1 比,像是某些节点的左右被对调了,这正是翻转。
5. 7从根开始:T1 的根是 50,T2 的根也是 50。先看这一对的值。
6. 850 和 50 相等,根这一层对上了。接下来要让它们的孩子也对上。
7. 9孩子有两种配法:「不翻」让 T1 左30 配 T2 左80、T1 右80 配 T2 右30;「翻」让 T1 左30 配 T2 右30、T1 右80 配 T2 左80。两种里只要有一种能让孩子全对上就行,先试不翻。
8. 10先试不翻:让 T1 的左孩子配 T2 的左孩子,也就是 30 配 80。看这一对。
9. 1130 和 80 不相等。不翻这种配法,头一对就对不上,所以「不翻」这条路走不通。那就改试「翻」。
10. 12改试翻:把 T1 的左配 T2 的右、T1 的右配 T2 的左。先看 T1 左孩子 30 配 T2 右孩子 30。
11. 1330 和 30 相等!这一对值对上了,但它们各自还有孩子,得递归进这两个 30 的子树继续比。
12. 14进到两个 30 的子树。先试不翻:T1 这个 30 的左孩子 20,配 T2 那个 30 的左孩子 40。
13. 1520 和 40 不相等,这层不翻又失败。再试翻:把 20 配到 T2 那个 30 的右孩子去。
14. 16翻转配法:T1 的 20 配 T2 那个 30 的右孩子 20。看这一对。
15. 1720 配 20,两个都是叶子、没有孩子,直接相等(都空的子树也相等)。这一对 ✓。
16. 18再看翻转配法的另一对:T1 的 40 配 T2 那个 30 的左孩子 40。
17. 1940 配 40,也是两个叶子,相等 ✓。两个孩子都对上了。
18. 20小结这棵 30 子树:在 30 这个节点处翻一下,20 配 20、40 配 40,整棵子树就对上了。所以「30 ↔ 30」这一对返回真。
19. 21回到根的翻转配法,还剩另一半:T1 的右孩子 80,配 T2 的左孩子 80。
20. 2280 配 80,两个叶子,相等 ✓。至此根的翻转配法两半都成立。
21. 23把翻过的地方圈出来:整个过程只在根 50 和左边那个 30 处各翻了一次(交换左右孩子),其它节点都保持原样。这两翻就能让 T1 变成 T2。
22. 24根这一层用翻转配法走通了:50 对 50,翻转后 30 配 30、80 配 80,而 30 子树里又翻了一次让 20、40 对上。整棵树在 50 和 30 处各翻一次就相等,所以返回 true。回头看,我们没真去搬动任何节点,只是每对节点试「不翻 或 翻」两种配法,一遍递归就判完。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List, Optional
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val=val; self.left=left; self.right=right
class Solution:
    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        if not root1 or not root2: return root1 is root2
        if root1.val != root2.val: return False
        return (self.flipEquiv(root1.left,root2.left) and self.flipEquiv(root1.right,root2.right)) or (self.flipEquiv(root1.left,root2.right) and self.flipEquiv(root1.right,root2.left))

#include <algorithm>
#include <functional>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode():val(0),left(nullptr),right(nullptr){} TreeNode(int x):val(x),left(nullptr),right(nullptr){} TreeNode(int x,TreeNode*l,TreeNode*r):val(x),left(l),right(r){}};
class Solution{public: bool flipEquiv(TreeNode* a,TreeNode* b){ if(!a||!b)return a==b; if(a->val!=b->val)return false; return (flipEquiv(a->left,b->left)&&flipEquiv(a->right,b->right))||(flipEquiv(a->left,b->right)&&flipEquiv(a->right,b->left)); }};

import java.util.*;
class TreeNode{int val;TreeNode left,right;TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val,TreeNode left,TreeNode right){this.val=val;this.left=left;this.right=right;}}
class Solution{ public boolean flipEquiv(TreeNode a,TreeNode b){ if(a==null||b==null)return a==b; if(a.val!=b.val)return false; return (flipEquiv(a.left,b.left)&&flipEquiv(a.right,b.right))||(flipEquiv(a.left,b.right)&&flipEquiv(a.right,b.left)); } }

复杂度

面试官可能追问