解題說明
Flip Equivalent Binary Trees
題目描述：
給定兩棵二元樹 root1 和 root2，判斷它們是否翻轉等價（flip equivalent）。翻轉操作是指：選擇任意節點，交換其左右子樹。如果經過若干次翻轉操作可以使兩棵樹相同，則它們翻轉等價。
解題思路： 遞迴比較：
兩棵樹翻轉等價，意味著在每個對應節點上，子樹要麼「直接匹配」（左對左、右對右），要麼「翻轉匹配」（左對右、右對左）。
遞迴判斷：
- 兩個節點都為空 → 等價。
- 其中一個為空或值不同 → 不等價。
- 遞迴檢查兩種配對方式：
- 不翻轉：
(left1, left2)且(right1, right2)都等價。 - 翻轉：
(left1, right2)且(right1, left2)都等價。 - 任一成立即可。
- 不翻轉：
C++ 解法
複雜度分析
時間複雜度：O(n) — 其中 n 是較小樹的節點數。每個節點最多被比較常數次。
空間複雜度：O(h) — 其中 h 是樹的高度，為遞迴棧的深度。最差情況 O(n)。
虛擬碼
1. flipEquiv(root1, root2):
a. If both null: return true.
b. If one is null or values differ: return false.
c. Return:
(flipEquiv(root1.left, root2.left) AND flipEquiv(root1.right, root2.right))
OR
(flipEquiv(root1.left, root2.right) AND flipEquiv(root1.right, root2.left)).其他解法
迭代法（BFS）：用兩個佇列同步遍歷兩棵樹。在每一層，對比當前節點的子節點：若值不匹配則嘗試交換後再比較。空間 O(n)，邏輯稍複雜。
正規化（Canonical Form）：將兩棵樹各自「正規化」（在每個節點，若左子值 > 右子值則交換），然後直接比較兩棵正規化後的樹是否相同。需要額外修改樹結構。
延伸思考
- 此遞迴的時間複雜度為什麼是 O(n) 而非 O(n^2)？每個節點的比較次數為什麼是常數？
- 如果兩棵樹非常不平衡（像鏈表），遞迴深度可能很深。如何轉為迭代以避免棧溢出？
- 「正規化」方法的思路是什麼？為什麼正規化後直接比較就能判斷翻轉等價？