951. Flip Equivalent Binary Trees

Flip Equivalent Binary Trees

題目描述： 給定兩棵二元樹 root1 和 root2，判斷它們是否翻轉等價（flip equivalent）。翻轉操作是指：選擇任意節點，交換其左右子樹。如果經過若干次翻轉操作可以使兩棵樹相同，則它們翻轉等價。

解題思路： 遞迴比較：

兩棵樹翻轉等價，意味著在每個對應節點上，子樹要麼「直接匹配」（左對左、右對右），要麼「翻轉匹配」（左對右、右對左）。

遞迴判斷：

1. 兩個節點都為空 → 等價。
2. 其中一個為空或值不同 → 不等價。
3. 遞迴檢查兩種配對方式：
   • 不翻轉：(left1, left2) 且 (right1, right2) 都等價。
   • 翻轉：(left1, right2) 且 (right1, left2) 都等價。
   • 任一成立即可。

時間複雜度：O(n) — 其中 n 是較小樹的節點數。每個節點最多被比較常數次。

空間複雜度：O(h) — 其中 h 是樹的高度，為遞迴棧的深度。最差情況 O(n)。

迭代法（BFS）：用兩個佇列同步遍歷兩棵樹。在每一層，對比當前節點的子節點：若值不匹配則嘗試交換後再比較。空間 O(n)，邏輯稍複雜。

正規化（Canonical Form）：將兩棵樹各自「正規化」（在每個節點，若左子值 > 右子值則交換），然後直接比較兩棵正規化後的樹是否相同。需要額外修改樹結構。

1. 此遞迴的時間複雜度為什麼是 O(n) 而非 O(n^2)？每個節點的比較次數為什麼是常數？
2. 如果兩棵樹非常不平衡（像鏈表），遞迴深度可能很深。如何轉為迭代以避免棧溢出？
3. 「正規化」方法的思路是什麼？為什麼正規化後直接比較就能判斷翻轉等價？