ホームページ >バックエンド開発 >PHPチュートリアル >バイナリー ツリー II のいとこ
バイナリー ツリー II のいとこ
- Linda Hamiltonオリジナル
- 2024-10-24 07:01:02497ブラウズ
2641。バイナリー ツリー II のいとこ
難易度: 中
トピック: ハッシュ テーブル、ツリー、深さ優先検索、幅優先検索、バイナリ ツリー
バイナリ ツリーのルートを指定すると、ツリー内の各ノードの値を すべてのいとこの値の合計 に置き換えます。
バイナリ ツリーの 2 つのノードは、異なる親を持つ同じ深さを持つ場合、いとことなります。
変更されたツリーのルートを返します。
ノードの深さは、ルート ノードからノードまでのパス内のエッジの数であることに注意してください。
例 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
- 5] の範囲内です。 1 4
ヒント:
- DFS を 2 回使用します。
- 初めて、二分木のすべてのレベルの値の合計を見つけます。
- 2 回目は、現在のレベルの値、つまり兄弟ノードの値の合計でノードの値を更新します。
解決策:
このソリューションでは、深さ優先検索 (DFS) アプローチを 2 回使用します。- 最初の 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 を設定し、次に 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]
-
最初の 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]
?>
いとこ値に基づくこの段階的な置換により、例に示すように変更されたツリーが生成されます。
まとめ
- このソリューションでは 2 つの DFS トラバーサルが使用されます。1 つは合計の計算に、もう 1 つはノード値の置換に使用されます。
- このロジックにより、バイナリ ツリーの構造を維持しながら、各ノードがそのいとこノードの値に基づいて更新されることが保証されます。
連絡先リンク
このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!
このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:
- GitHub
以上がバイナリー ツリー II のいとこの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
声明：
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。