951. Flip Equivalent Binary Trees

Medium
Description

對一棵二元樹，我們可以選擇任意節點並交換其左右子樹。若經過若干次翻轉後兩棵樹相同，則稱它們是翻轉等價的。判斷兩棵二元樹是否翻轉等價。

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#

兩棵樹翻轉等價，代表對應節點的值相同，且子樹要嘛直接匹配、要嘛交叉匹配。

  • 兩個節點值相同時，有兩種可能：
    • 左對左、右對右（不翻轉）
    • 左對右、右對左（翻轉）
  • 只要其中一種成立即可

Approaches#

1: 遞迴比較#

  • 概念: 遞迴檢查每對節點，值相同時嘗試兩種配對方式
  • 時間複雜度: O(n)，每個節點最多訪問一次
  • 空間複雜度: 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: 正規化後比較#

  • 概念: 將兩棵樹「正規化」——每個節點保證左子值小於右子值，然後直接比較是否相同
  • 時間複雜度: O(n)
  • 空間複雜度: 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: 翻轉等價 = 值相同 + 子樹配對（直接或交叉）
  • 關鍵技巧: 遞迴的兩種配對方式用 || 連接，短路求值讓平均效能很好；正規化方法將問題轉化為簡單的相等比較