2641。バイナリー ツリー II のいとこ

難易度: 中

トピック: ハッシュ テーブル、ツリー、深さ優(yōu)先検索、幅優(yōu)先検索、バイナリ ツリー

バイナリ ツリーのルートを指定すると、ツリー內(nèi)の各ノードの値を すべてのいとこの値の合計(jì) に置き換えます。

バイナリ ツリーの 2 つのノードは、異なる親を持つ同じ深さを持つ場合、いとことなります。

変更されたツリーのルートを返します。

ノードの深さは、ルート ノードからノードまでのパス內(nèi)のエッジの數(shù)であることに注意してください。

例 1:

• 入力: root = [5,4,9,1,10,null,7]
• 出力: [0,0,0,7,7,null,11]
• 説明: 上の図は、初期の二分木と各ノードの値を変更した後の二分木を示しています。
  値 5 のノードにはいとこがないため、合計(jì)は 0 になります。
  値 4 のノードにはいとこがないため、合計(jì)は 0 です。
  値 9 のノードにはいとこがないため、合計(jì)は 0 になります。
  値 1 のノードには値 7 のいとこがあるため、その合計(jì)は 7 になります。
  値 10 のノードには値 7 のいとこがあるため、その合計(jì)は 7 になります。
  値 7 のノードには値 1 と 10 のいとこがあるため、その合計(jì)は 11 になります。

例 2:

• 入力: root = [3,1,2]
• 出力: [0,0,0]
• 説明: 上の図は、初期の二分木と各ノードの値を変更した後の二分木を示しています。
  値 3 のノードにはいとこがないため、合計(jì)は 0 になります。
  値 1 のノードにはいとこがないため、合計(jì)は 0 になります。
  値 2 のノードにはいとこがないため、合計(jì)は 0 です。

制約:

ツリー內(nèi)のノードの數(shù)は [1, 10
• 5^{] の範(fàn)囲內(nèi)です。}
1 4

ヒント:

DFS を 2 回使用します。
初めて、二分木のすべてのレベルの値の合計(jì)を見つけます。
2 回目は、現(xiàn)在のレベルの値、つまり兄弟ノードの値の合計(jì)でノードの値を更新します。

解決策:

このソリューションでは、深さ優(yōu)先検索 (DFS) アプローチを 2 回使用します。

1. 最初の DFS: ツリーの各レベルのすべてのノード値の合計(jì)を計(jì)算します。
2. 2 番目の DFS: そのレベルの合計(jì)から兄弟の値を減算し、その従兄弟の値の合計(jì)で各ノードの値を更新します。

このソリューションを 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]
?>

コードの內(nèi)訳

1. replaceValueInTree メソッド

• これはプロセスを初期化するメインメソッドです。
• 各レベルの値の合計(jì)を保持する空の配列 $levelSums を作成します。
• 最初の DFS を呼び出して $levelSums を設(shè)定し、次に 2 番目の DFS を呼び出してツリー內(nèi)の値を置き換えます。

2. dfs方式（第一DFS）

• パラメータ:

  • $root: 現(xiàn)在のノード。
  • $level: ツリーの現(xiàn)在の深さレベル。
  • &$levelSums: 合計(jì)が保存される配列への參照。

• 基本ケース: ノードが null の場合、戻ります。

• 現(xiàn)在のレベルの合計(jì)が初期化されていない場合 (つまり、レベルが配列に存在しない場合)、それを 0 に初期化します。

• 現(xiàn)在のノードの値をそのレベルの合計(jì)に加算します。

• 左と右の子に対して dfs を再帰的に呼び出し、レベルを 1 ずつ増やします。

3. replace メソッド (2 番目の DFS)

• パラメータ:

  • $root: 現(xiàn)在のノード。
  • $level: 現(xiàn)在の深度レベル。
  • $curr: 変更されたツリー內(nèi)の現(xiàn)在のノード。
  • $levelSums: 各レベルの合計(jì)を含む配列。

• いとこの値の合計(jì)を計(jì)算します:

  • 次のレベルの合計(jì)を取得します。
  • この合計(jì)から現(xiàn)在のノードの子 (兄弟) の値を引いて、いとこの合計(jì)を取得します。

• 左の子が存在する場合は、いとこの合計(jì)を使用して新しい TreeNode を作成し、それに対して replace を再帰的に呼び出します。

• 正しい子が存在する場合は、正しい子に対して同じことを行います。

チュートリアルの例

プロンプトの最初の例を使用してみましょう:

入力

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

1. 最初の DFS (レベル合計(jì)の計(jì)算):

   • レベル 0: 5 → 合計(jì) = 5
   • レベル 1: 4 9 → 合計(jì) = 13
   • レベル 2: 1 10 7 → 合計(jì) = 18
   • 最終レベルの合計(jì): [5, 13, 18]

2. 2 番目の DFS (値の置換):

   • レベル 0: 5 にはいとこがない → 0 に置き換えます。
   • レベル 1:
     • 4 → いとこ = 9 → 9 に置き換えます (合計(jì)レベル 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]
?>

いとこ値に基づくこの段階的な置換により、例に示すように変更されたツリーが生成されます。

まとめ

• このソリューションでは 2 つの DFS トラバーサルが使用されます。1 つは合計(jì)の計(jì)算に、もう 1 つはノード値の置換に使用されます。
• このロジックにより、バイナリ ツリーの構(gòu)造を維持しながら、各ノードがそのいとこノードの値に基づいて更新されることが保証されます。

連絡(luò)先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お?dú)荬巳毪辘违僵`シャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お?dú)葺Xにフォローしてください:

• LinkedIn
• GitHub

以上がバイナリー ツリー II のいとこの詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國語 Web サイトの他の関連記事を參照してください。