二叉树 II 中的表兄弟

2641。二叉树 II 中的表兄弟

难度：中等

主题： 哈希表、树、深度优先搜索、广度优先搜索、二叉树

给定二叉树的根，将树中每个节点的值替换为所有表兄弟值的总和。

二叉树的两个节点是表兄弟，如果它们具有相同的深度且具有不同的父节点。

返回修改后的树的根。

注意节点的深度是从根节点到它的路径中的边数。

示例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⁵] 范围内。
• 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中文网其他相关文章！