。翻轉等效二元樹

951。翻轉等效二元樹

難度：中

主題：樹、深度優先搜尋、二元樹

對於二元樹T，我們可以定義一個翻轉操作，如下：選擇任意節點，交換左右子樹。

二元樹X翻轉等價於二元樹Y當且僅當我們可以使X等於 > 經過一定次數的翻轉操作。

給定兩個二元樹 root1 和 root2 的根，如果兩棵樹翻轉等價，則回傳

true，否則回傳 false.

範例1：

• 輸入： root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5 ,空,空,空,空,8,7]
• 輸出： true
• 解釋：我們翻轉值為 1、3 和 5 的節點。

範例2：

• 輸入： root1 = [], root2 = []
• 輸出： true

範例 3：

• 輸入： root1 = [], root2 = [1]
• 輸出： false

約束：

每棵樹的節點數在 [0, 100] 範圍內。
每棵樹都有唯一的節點值，範圍為 [0, 99]。

解：

我們可以使用遞歸深度優先搜尋（DFS）。這個想法是，如果兩棵樹的根值相同，並且子樹相同（沒有任何翻轉），或者在某些節點翻轉左右子樹後它們變得相同，則它們是翻轉等價的。

計劃：

1. 基本案例：

   如果 root1 和 root2 都為空，則它們是簡單翻轉等價的。
   如果其中只有一個為空，則它們不能等價。
   如果root1和root2的根值不同，則它們不能相等。

2. 遞迴案例：

   遞迴檢查兩種可能性：
   • root1 的左子樹翻轉相當於 root2 的左子樹，root1 的右子樹翻轉相當於 root2 的右子樹（即不翻轉）。
     root1 的左子樹翻轉相當於 root2 的右子樹，root1 的右子樹翻轉相當於 root2 的左子樹（即翻轉孩子）。

讓我們用 PHP 實作這個解：

951。翻轉等效二元樹

解釋：

1. TreeNode 類別：TreeNode 類別表示二元樹中的節點，具有建構子來初始化節點的值、左子節點和右子節點。

2. flipEquiv 函數:

   • 基本情況處理兩個節點都為空、一個節點為空或值不符的情況。
   • 遞歸情況檢查兩種可能性（不翻轉與翻轉），確保子樹在任一條件下翻轉等效。

時間複雜度：

• 此函數檢查兩棵樹中的每個節點，並且每個遞歸呼叫處理兩個子樹。因此，時間複雜度為 O(N)，其中 N 是樹中的節點數。

空間複雜度：

• 由於遞歸堆疊，空間複雜度為 O(H)，其中 H 是樹的高度。在最壞的情況下（對於傾斜的樹），這可能是 O(N)。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是。翻轉等效二元樹的詳細內容。更多資訊請關注PHP中文網其他相關文章！