2641。二叉树 II 中的表兄弟
难度：中等
主题： 哈希表、树、深度优先搜索、广度优先搜索、二叉树
给定二叉树的根，将树中每个节点的值替换为所有表兄弟值的总和。
二叉树的两个节点是表兄弟，如果它们具有相同的深度且具有不同的父节点。
返回修改后的树的根。
注意节点的深度是从根节点到它的路径中的边数。
示例1：
示例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]
?>
参数：
基本情况：如果节点为空，则返回。
如果当前级别的总和未初始化（即该级别在数组中不存在），则将其初始化为 0。
将当前节点的值添加到其级别的总和中。
对左右子节点递归调用 dfs，级别加 1。
参数：
计算表兄弟的值的总和：
如果左子节点存在，则使用表兄弟的总和创建一个新的 TreeNode，并递归调用替换它。
如果右孩子存在，则对右孩子做同样的事情。
让我们使用提示中的第一个示例：
root = [5,4,9,1,10,null,7]
第一次 DFS（计算级别总和）：
第二个 DFS（替换值）：
<?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]
?>
这种基于表兄弟值的逐步替换会产生修改后的树，如示例所示。
联系链接
如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！
如果您想要更多类似的有用内容，请随时关注我：
以上是二叉树 II 中的表兄弟的详细内容。更多信息请关注PHP中文网其他相关文章！
