反轉二元樹的奇數層

2415。反轉二元樹的奇數層

難度：中

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

給定一個完美二元樹的根，反轉樹的每個奇數層的節點值。

• 例如，假設第3層的節點值為[2,1,3,4,7,11,29,18]，那麼它應該變成[18,29,11,7,4,3,1 ,2].

回傳反轉樹的根。

如果所有父節點都有兩個子節點並且所有葉子都位於同一級別，那麼二叉樹就是完美。

節點的等級是它與根節點之間的路徑上的邊數。

範例1：

• 輸入： root = [2,3,5,8,13,21,34]
• 輸出： [2,5,3,8,13,21,34]
• 說明：
  • 樹只有一層奇數。
  • 第1層的節點分別是3、5，顛倒變成5、3。

範例2：

• 輸入： root = [7,13,11]
• 輸出： [7,11,13]
• 說明：
  • 第1層的節點是13, 11，顛倒變成11, 13。

範例 3：

• 輸入： root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
• 輸出： [0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]
• 說明：
  • 奇數等級具有非零值。
  • 第 1 層的節點為 1, 2，反轉後為 2, 1。
  • 第 3 層的節點為 1, 1, 1, 1, 2, 2, 2, 2，反轉後為 2, 2, 2, 2, 1, 1, 1, 1。

約束：

• 樹中的節點數量在 [1, 2¹⁴] 範圍內。
• 0 5
• 根是完美二元樹。

提示：

1. 嘗試獨立遞歸地解決每個等級。
2. 執行深度優先搜尋時，將左右節點（應成對）傳遞到下一層。如果當前等級是奇數，則反轉它們的值，否則遞歸移動到下一個等級。

解：

我們需要對二元樹進行深度優先遍歷。任務是反轉奇數層的節點值。完美二元樹意味著所有非葉節點都有兩個子節點，並且所有葉節點都處於同一層級。

我們將使用 DFS（深度優先搜尋）方法，並且在每個奇數層級上，我們將反轉節點值。以下是實現此目的的解決方案。

要點：

• 這棵樹是完美的，這意味著它是完全平衡的，並且所有葉節點都在同一級別。
• 只有奇數層的節點需要反轉。奇數等級從等級 1 開始索引（第 1、第 3、第 5 等）。
• DFS可用於遍歷樹並識別節點的層級。當我們遇到奇數層級時，我們交換該層級的節點值。
• 在每一層，我們遍歷兩個子節點：左子節點和右子節點。

方法：

1. 對樹進行深度優先遍歷。
2. 對於目前層級的每對節點：
   • 如果等級為奇數，則交換節點值。
3. 遞歸處理目前節點的左右子節點，傳遞更新的層級資訊。
4. 處理整棵樹後回到根節點。

計劃：

1. 從根節點開始。
2. 使用遞歸函數 dfs 遍歷樹並反轉奇數層的節點值。
3. 追蹤當前等級以識別奇怪的等級。
4. 交換奇數層的值並繼續對子級進行 DFS 遍歷。
5. 處理後返回root。

解決步驟：

1. 定義一個遞歸函數 dfs($left, $right, $isOddLevel)：
   • left：左子節點。
   • right：右子節點。
   • isOddLevel: 布林值，表示目前等級是否為奇數。
2. 檢查 left 是否為空。如果是，則返回，因為沒有更多節點需要處理。
3. 如果 isOddLevel 為 true，則交換左右節點的值。
4. 遞迴呼叫 dfs 函數：
   • 左孩子的左孩子和右孩子的右孩子（下一級）。
   • 左孩子的右孩子和右孩子的左孩子（下一級）。
5. 使用 dfs($root->left, $root->right, true) 開始遞歸並傳回根。

讓我們用 PHP 實作這個解：2415。反轉二元樹的奇數層

<?php
class TreeNode {
    public $val = 0;
    public $left = null;
    public $right = null;

    public function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    /**
     * @param TreeNode $root
     * @return TreeNode
     */
    public function reverseOddLevels($root) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Helper function to perform DFS
     *
     * @param $left
     * @param $right
     * @param $isOddLevel
     * @return void
     */
    private function dfs($left, $right, $isOddLevel) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Example usage:
$root = new TreeNode(2);
$root->left = new TreeNode(3);
$root->right = new TreeNode(5);
$root->left->left = new TreeNode(8);
$root->left->right = new TreeNode(13);
$root->right->left = new TreeNode(21);
$root->right->right = new TreeNode(34);

$solution = new Solution();
$reversedRoot = $solution->reverseOddLevels($root);

// Function to print the tree for testing
function printTree($root) {
    if ($root === null) {
        return;
    }
    echo $root->val . " ";
    printTree($root->left);
    printTree($root->right);
}

printTree($reversedRoot); // Output: 2 5 3 8 13 21 34
?>

解釋：

1. TreeNode 類別：表示二元樹節點的結構，該節點有一個值（val）和兩個子節點（左、右）。
2. reverseOddLevels 函數：以根節點的左右子節點啟動 DFS，並從層級 1（奇數層級）開始。
3. dfs 函數：
   • 接受兩個節點（左和右）和一個布林值 isOddLevel 來確定目前等級是否為奇數。
   • 如果目前等級為奇數，則交換 left 和 right 的值。
   • 遞歸地呼叫自身進入下一個級別，交替 isOddLevel 值（true 變成 false，反之亦然）。
4. 遞歸繼續處理每個層級的下一對節點，確保僅奇數層級的節點被反轉。

演練範例：

範例1：

輸入：

       2
      / \
     3   5
    / \ / \
   8 13 21 34

• 0級：[2]（偶數，無變化）。
• 第 1 級：[3, 5]（奇數，與 [5, 3] 相反）。
• 第 2 級：[8, 13, 21, 34]（偶數，無變化）。

輸出：

       2
      / \
     5   3
    / \ / \
   8 13 21 34

範例2：

輸入：

       7
      / \
     13  11

• 0級：[7]（偶數，無變化）。
• 第 1 級：[13, 11]（奇數，與 [11, 13] 相反）。

輸出：

       7
      / \
     11  13

時間複雜度：

• 時間複雜度：O(n)，其中n是二元樹中的節點數。我們以深度優先的方式訪問每個節點一次。
• 空間複雜度：O(h)，其中h是樹的高度。遞歸深度對應於樹的高度，在最壞的情況下（對於傾斜樹），它將是 O(n)，但對於完美二元樹，它是 O(log n)。

此解決方案使用時間複雜度為 O(n) 的深度優先搜尋有效地反轉完美二元樹奇數層的節點。該程式碼在奇數層級交換值並使用遞歸方法來處理樹。

聯絡連結

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

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

• 領英
• GitHub

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