首頁 > 後端開發 > php教程 > 二元樹 II 中的表兄弟

二元樹 II 中的表兄弟

Linda Hamilton
發布: 2024-10-24 07:01:02
原創
465 人瀏覽過

2641。二元樹 II 中的表兄弟

難度:

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

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

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

回傳修改後的樹的根

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

範例1:

Cousins in Binary Tree II

  • 輸入: 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:

Cousins in Binary Tree II

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

約束:

  • 樹中的節點數量在 [1, 105] 範圍內。
  • 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中文網其他相關文章!

來源:dev.to
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
作者最新文章
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板