简体中文(ZH-CN) English(EN) 繁体中文(ZH-TW) 日本語(JA) 한국어(KO) Melayu(MS) Français(FR) Deutsch(DE)
ホームページ > バックエンド開発 > PHPチュートリアル > 本文

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

Linda Hamilton
リリース： 2024-10-24 07:01:02
オリジナル
390 人が閲覧しました

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

難易度: 中

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

バイナリ ツリーのルートを指定すると、ツリー内の各ノードの値を すべてのいとこの値の合計 に置き換えます。

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

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

ノードの深さは、ルート ノードからノードまでのパス内のエッジの数であることに注意してください。

例 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, 10
  • 5] の範囲内です。
    • 1 4

ヒント:

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

解決策:

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

  1. 最初の DFS: ツリーの各レベルのすべてのノード値の合計を計算します。
  2. 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 を設定し、次に 2 番目の DFS を呼び出してツリー内の値を置き換えます。

2. dfs方式（第一DFS）

  • パラメータ:

    • $root: 現在のノード。
    • $level: ツリーの現在の深さレベル。
    • &$levelSums: 合計が保存される配列への参照。

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

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

  • 現在のノードの値をそのレベルの合計に加算します。

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

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

  • パラメータ:

    • $root: 現在のノード。
    • $level: 現在の深度レベル。
    • $curr: 変更されたツリー内の現在のノード。
    • $levelSums: 各レベルの合計を含む配列。

  • いとこの値の合計を計算します:

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

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

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

チュートリアルの例

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

入力 

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. 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]
?>
ログイン後にコピー
ログイン後にコピー

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

まとめ

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

連絡先リンク

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

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

  • LinkedIn
  • GitHub

以上がバイナリー ツリー II のいとこの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

ソース：dev.to
前の記事：完全な単語を尊重しながらテキストを 100 文字に切り詰める方法 次の記事：PHP SimpleXML を使用した「入力は適切な UTF-8 ではありません。エンコーディングが示されています !」エラーを解決する方法?
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
著者別の最新記事
最新の問題
function_exists() はカスタム関数を決定できません Function test () {return true;} if (function_exists ('test')) {echo "テストは関数です";
から 2024-04-29 11:01:01
0
2
1667
Google Chromeのモバイル版を表示する方法 こんにちは、先生、Google Chrome をモバイル版に変更するにはどうすればよいですか?
から 2024-04-23 00:22:19
0
10
1819
子ウィンドウは親ウィンドウを操作しますが、出力は応答しません。 最初の 2 つの文は実行可能ですが、最後の文は実装できません。
から 2024-04-19 15:37:47
0
1
1545
親ウィンドウには出力がありません document.onclick = function(){ window.opener.document.write('私は子ウィンドウの出力です');
から 2024-04-18 23:52:34
0
1
1455
CSS マインド マッピングに関するコースウェアはどこにありますか? コースウェア
から 2024-04-16 10:10:18
0
0
1505
関連トピック
詳細>
人気のおすすめ
人気のチュートリアル
詳細>
関連するチュートリアル
人気のおすすめ
最新のコース
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート
私たちについて 免責事項 Sitemap
PHP中国語ウェブサイト：福祉オンライン PHP トレーニング，PHP 学習者の迅速な成長を支援します！