二元樹 II 中的表兄弟

2641。二元樹 II 中的表兄弟

難度：中

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

給定二元樹的根，將樹中每個節點的值替換為所有表兄弟值的總和。

二元樹的兩個節點是表兄弟，如果它們具有相同的深度且具有不同的父節點。

回傳修改後的樹的根。

注意節點的深度是從根節點到它的路徑中的邊數。

範例1：

• 輸入： root = [5,4,9,1,10,null,7]
• 輸出： [0,0,0,7,7,null,11]
• 說明：上圖展示了初始二元樹和改變每個節點的值後的二元樹。
  • 值為 5 的節點沒有任何表兄弟，因此其總和為 0。
  • 值為 4 的節點沒有任何表兄弟，因此其總和為 0。
  • 值為 9 的節點沒有任何表兄弟，因此其總和為 0。
  • 值為 1 的節點有一個值為 7 的表兄弟，因此它的總和為 7。
  • 值為 10 的節點有一個值為 7 的表兄弟，因此其和為 7。
  • 值為 7 的節點有值為 1 和 10 的表兄弟，因此其總和為 11。

範例2：

• 輸入： root = [3,1,2]
• 輸出： [0,0,0]
• 說明：上圖展示了初始二元樹和改變每個節點的值後的二元樹。
  • 值為 3 的節點沒有任何表兄弟，因此其總和為 0。
  • 值為 1 的節點沒有任何表兄弟，因此其總和為 0。
  • 值為 2 的節點沒有任何表兄弟，因此其總和為 0。

約束：

• 樹中的節點數量在 [1, 10⁵] 範圍內。
• 1 4

提示：

1. 使用 DFS 兩次。
2. 第一次求二元樹所有層的值總和。
3. 第二次，用目前層級的值-兄弟節點的值總和來更新節點的值。

解：

此解決方案兩次使用深度優先搜尋 (DFS) 方法：

1. 第一次 DFS： 計算樹每一層所有節點值的總和。
2. 第二個 DFS： 透過從該層級的總數中減去其兄弟節點的值，用其表兄弟節點的值總和來更新每個節點的值。

讓我們用 PHP 實作這個解：2641。二元樹 II 中的表兄弟

<?php
// Definition for a binary tree node.
class TreeNode {
    public $val = null;
    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 replaceValueInTree($root) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * DFS to calculate the sum of node values at each level.
     * @param $root - current node
     * @param $level - current depth level in the tree
     * @param $levelSums - array holding the sum of values at each level
     * @return void
     */
    private function dfs($root, $level, &$levelSums) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * DFS to replace the node values with the sum of cousins' values.
     * @param $root - current node in the original tree
     * @param $level - current depth level in the tree
     * @param $curr - node being modified in the new tree
     * @param $levelSums - array holding the sum of values at each level
     * @return mixed
     */
    private function replace($root, $level, $curr, $levelSums) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Helper function to print the tree (for testing purpose)
function printTree($root) {
    if ($root === null) return [];

    $result = [];
    $queue = [$root];

    while (!empty($queue)) {
        $node = array_shift($queue);
        if ($node !== null) {
            $result[] = $node->val;
            $queue[] = $node->left;
            $queue[] = $node->right;
        } else {
            $result[] = null;
        }
    }

    // Remove trailing null values for clean output
    while (end($result) === null) {
        array_pop($result);
    }

    return $result;
}

// Example usage:

// Tree: [5,4,9,1,10,null,7]
$root = new TreeNode(5);
$root->left = new TreeNode(4);
$root->right = new TreeNode(9);
$root->left->left = new TreeNode(1);
$root->left->right = new TreeNode(10);
$root->right->right = new TreeNode(7);

$solution = new Solution();
$modifiedTree = $solution->replaceValueInTree($root);

print_r(printTree($modifiedTree));  // Output: [0, 0, 0, 7, 7, null, 11]
?>

程式碼細目

1.replaceValueInTree方法

• 這是初始化進程的主要方法。
• 它建立一個空數組 $levelSums，用於保存每個層級的值的總和。
• 它呼叫第一個 DFS 來填入 $levelSums，然後呼叫第二個 DFS 來取代樹中的值。

2. dfs方法（第一次DFS）

• 參數：

  • $root：當前節點。
  • $level：樹的目前深度等級。
  • &$levelSums：儲存總和的陣列的參考。

• 基本情況：如果節點為空，則回傳。

• 如果目前層級的總和未初始化（即該層級在陣列中不存在），則將其初始化為 0。

• 將目前節點的值加到其等級的總和。

• 對左右子節點遞歸呼叫 dfs，層級加 1。

3.替換方法（第二個DFS）

• 參數：

  • $root：當前節點。
  • $level：目前深度等級。
  • $curr：修改樹中的目前節點。
  • $levelSums：每個等級的總和的陣列。

• 計算表兄弟的值的總和：

  • 取得下一層級的總和。
  • 從總數中減去目前節點的子節點（兄弟姊妹）的值即可得到表兄弟的總和。

• 如果左子節點存在，則使用表格兄弟的總和建立新的 TreeNode，並遞歸呼叫取代它。

• 如果右孩子存在，則對右孩子做同樣的事情。

範例演練

讓我們使用提示中的第一個範例：

輸入

root = [5,4,9,1,10,null,7]

1. 第一次 DFS（計算等級總和）：

   • 0 級：5 → 總和 = 5
   • 第 1 級：4 9 → 總和 = 13
   • 第 2 級：1 10 7 → 總和 = 18
   • 最終關卡總和：[5, 13, 18]

2. 第二個 DFS（替換值）：

   • 在 0 級：5 沒有表兄弟 → 替換為 0。
   • 1 級：
     • 4 → 表兄弟 = 9 → 替換為 9（來自第 1 級總計，沒有兄弟姐妹）。
     • 9 → 表兄弟 = 4 → 替換為 4。
   • 2 級：
     • 1 → 表兄弟 = 10 7 = 17 → 替換為 17。
     • 10 → 表兄弟 = 1 7 = 8 → 替換為 8。
     • 7 → 表兄弟 = 1 10 = 11 → 替換為 11。

輸出

<?php
// Definition for a binary tree node.
class TreeNode {
    public $val = null;
    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 replaceValueInTree($root) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * DFS to calculate the sum of node values at each level.
     * @param $root - current node
     * @param $level - current depth level in the tree
     * @param $levelSums - array holding the sum of values at each level
     * @return void
     */
    private function dfs($root, $level, &$levelSums) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * DFS to replace the node values with the sum of cousins' values.
     * @param $root - current node in the original tree
     * @param $level - current depth level in the tree
     * @param $curr - node being modified in the new tree
     * @param $levelSums - array holding the sum of values at each level
     * @return mixed
     */
    private function replace($root, $level, $curr, $levelSums) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Helper function to print the tree (for testing purpose)
function printTree($root) {
    if ($root === null) return [];

    $result = [];
    $queue = [$root];

    while (!empty($queue)) {
        $node = array_shift($queue);
        if ($node !== null) {
            $result[] = $node->val;
            $queue[] = $node->left;
            $queue[] = $node->right;
        } else {
            $result[] = null;
        }
    }

    // Remove trailing null values for clean output
    while (end($result) === null) {
        array_pop($result);
    }

    return $result;
}

// Example usage:

// Tree: [5,4,9,1,10,null,7]
$root = new TreeNode(5);
$root->left = new TreeNode(4);
$root->right = new TreeNode(9);
$root->left->left = new TreeNode(1);
$root->left->right = new TreeNode(10);
$root->right->right = new TreeNode(7);

$solution = new Solution();
$modifiedTree = $solution->replaceValueInTree($root);

print_r(printTree($modifiedTree));  // Output: [0, 0, 0, 7, 7, null, 11]
?>

這種基於表兄弟值的逐步替換會產生修改後的樹，如範例所示。

概括

• 此解決方案使用兩次 DFS 遍歷：一次用於計算總和，另一個用於替換節點值。
• 邏輯確保每個節點根據其表兄弟節點的值進行更新，同時保持二元樹的結構。

聯絡連結

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

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

• 領英
• GitHub

以上是二元樹 II 中的表兄弟的詳細內容。更多資訊請關注PHP中文網其他相關文章！