對一棵二元樹，我們可以選擇任意節點並交換其左右子樹。若經過若干次翻轉後兩棵樹相同，則稱它們是翻轉等價的。判斷兩棵二元樹是否翻轉等價。
Example:
Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7] Output: true
Intuition
TIP
兩棵樹翻轉等價，代表對應節點的值相同，且子樹要嘛直接匹配、要嘛交叉匹配。
- 兩個節點值相同時，有兩種可能：
- 左對左、右對右（不翻轉）
- 左對右、右對左（翻轉）
- 只要其中一種成立即可
Approaches
1. Recursive Compare — O(n) / O(h)
- Idea: 遞迴檢查每對節點，值相同時嘗試兩種配對方式
- Time:
O(n)，每個節點最多訪問一次 - Space:
O(h)，h 為樹高
class Solution {
fun flipEquiv(root1: TreeNode?, root2: TreeNode?): Boolean {
if (root1 == null && root2 == null) return true
if (root1 == null || root2 == null) return false
if (root1.`val` != root2.`val`) return false
// 不翻轉 或 翻轉
return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) ||
(flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left))
}
}⭐ 2. Normalize then Compare — O(n) / O(h)
- Idea: 將兩棵樹「正規化」——每個節點保證左子值小於右子值，然後直接比較是否相同
- Time:
O(n) - Space:
O(h)
class Solution {
fun flipEquiv(root1: TreeNode?, root2: TreeNode?): Boolean {
canonicalize(root1)
canonicalize(root2)
return isSame(root1, root2)
}
private fun canonicalize(node: TreeNode?) {
if (node == null) return
val leftVal = node.left?.`val` ?: Int.MAX_VALUE
val rightVal = node.right?.`val` ?: Int.MAX_VALUE
if (leftVal > rightVal) {
val temp = node.left
node.left = node.right
node.right = temp
}
canonicalize(node.left)
canonicalize(node.right)
}
private fun isSame(a: TreeNode?, b: TreeNode?): Boolean {
if (a == null && b == null) return true
if (a == null || b == null) return false
return a.`val` == b.`val` && isSame(a.left, b.left) && isSame(a.right, b.right)
}
}🔑 Takeaways
- Pattern: 翻轉等價 = 值相同 + 子樹配對（直接或交叉）
- Key trick: 遞迴的兩種配對方式用
||連接，短路求值讓平均效能很好；正規化方法將問題轉化為簡單的相等比較