2415。反轉(zhuǎn)二元樹的奇數(shù)層

難度：中

主題：樹、深度優(yōu)先搜尋、廣度優(yōu)先搜尋、二元樹

給定一個完美二元樹的根，反轉(zhuǎn)樹的每個奇數(shù)層的節(jié)點值。

• 例如，假設(shè)第3層的節(jié)點值為[2,1,3,4,7,11,29,18]，那麼它應(yīng)該變成[18,29,11,7,4,3,1 ,2].

回傳反轉(zhuǎn)樹的根。

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

節(jié)點的等級是它與根節(jié)點之間的路徑上的邊數(shù)。

範(fàn)例1：

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

範(fàn)例2：

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

範(fàn)例 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]
• 說明：
  • 奇數(shù)等級具有非零值。
  • 第 1 層的節(jié)點為 1, 2，反轉(zhuǎn)後為 2, 1。
  • 第 3 層的節(jié)點為 1, 1, 1, 1, 2, 2, 2, 2，反轉(zhuǎn)後為 2, 2, 2, 2, 1, 1, 1, 1。

約束：

• 樹中的節(jié)點數(shù)量在 [1, 2¹⁴] 範(fàn)圍內(nèi)。
• 0 5
• 根是完美二元樹。

提示：

1. 嘗試獨立遞歸地解決每個等級。
2. 執(zhí)行深度優(yōu)先搜尋時，將左右節(jié)點（應(yīng)成對）傳遞到下一層。如果當(dāng)前等級是奇數(shù)，則反轉(zhuǎn)它們的值，否則遞歸移動到下一個等級。

解：

我們需要對二元樹進(jìn)行深度優(yōu)先遍歷。任務(wù)是反轉(zhuǎn)奇數(shù)層的節(jié)點值。完美二元樹意味著所有非葉節(jié)點都有兩個子節(jié)點，並且所有葉節(jié)點都處於同一層級。

我們將使用 DFS（深度優(yōu)先搜尋）方法，並且在每個奇數(shù)層級上，我們將反轉(zhuǎn)節(jié)點值。以下是實現(xiàn)此目的的解決方案。

要點：

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

方法：

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

計劃：

1. 從根節(jié)點開始。
2. 使用遞歸函數(shù) dfs 遍歷樹並反轉(zhuǎn)奇數(shù)層的節(jié)點值。
3. 追蹤當(dāng)前等級以識別奇怪的等級。
4. 交換奇數(shù)層的值並繼續(xù)對子級進(jìn)行 DFS 遍歷。
5. 處理後返回root。

解決步驟：

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

讓我們用 PHP 實作這個解：2415。反轉(zhuǎn)二元樹的奇數(shù)層

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

演練範(fàn)例：

範(fàn)例1：

輸入：

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

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

輸出：

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

範(fàn)例2：

輸入：

       7
      / \
     13  11

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

輸出：

       7
      / \
     11  13

時間複雜度：

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

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

聯(lián)絡(luò)連結(jié)

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

如果您想要更多類似的有用內(nèi)容，請隨時關(guān)注我：

• 領(lǐng)英
• GitHub

以上是反轉(zhuǎn)二元樹的奇數(shù)層的詳細(xì)內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！