Medium

题目描述

给你一棵二叉树的根 root ，请你将每个节点的值替换为该节点的所有表兄弟节点值的和。

如果两个节点在树中有相同的深度且它们的父节点不同，则它们互为表兄弟。

返回修改后树的根。

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

示例 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 <= Node.val <= 10^4

解题思路

解题思路

这道题的关键在于理解表兄弟节点的定义：同一层的不同父节点的子节点。

解决这个问题需要两次遍历：

第一次遍历：计算每一层的节点值总和。我们可以使用BFS层序遍历，记录每一层所有节点的值之和。

第二次遍历：更新每个节点的值。对于每个节点，其新值 = 当前层的总和 - 兄弟节点的值之和。这里的兄弟节点指的是同一个父节点的所有子节点。

具体实现步骤：

  1. 第一次BFS遍历，用数组记录每层的节点值总和
  2. 第二次BFS遍历，对于每个节点的子节点们：
    • 计算子节点们的值之和（兄弟节点和）
    • 每个子节点的新值 = 下一层总和 - 兄弟节点和
  3. 根节点没有表兄弟，直接设为0

这种方法的优势在于思路清晰，易于理解和实现。时间复杂度为O(n)，空间复杂度为O(n)，其中n是树中节点的数量。

代码实现

class Solution {
public:
    TreeNode* replaceValueInTree(TreeNode* root) {
        if (!root) return root;
        
        // 第一次BFS：计算每层的总和
        vector<int> levelSum;
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            int size = q.size();
            int sum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                sum += node->val;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            levelSum.push_back(sum);
        }
        
        // 第二次BFS：更新节点值
        q.push(root);
        root->val = 0; // 根节点没有表兄弟
        int level = 0;
        
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                
                // 计算子节点的兄弟节点和
                int siblingSum = 0;
                if (node->left) siblingSum += node->left->val;
                if (node->right) siblingSum += node->right->val;
                
                // 更新子节点值
                if (node->left) {
                    node->left->val = levelSum[level + 1] - siblingSum;
                    q.push(node->left);
                }
                if (node->right) {
                    node->right->val = levelSum[level + 1] - siblingSum;
                    q.push(node->right);
                }
            }
            level++;
        }
        
        return root;
    }
};

class Solution:
    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return root
        
        # 第一次BFS：计算每层的总和
        level_sum = []
        queue = [root]
        
        while queue:
            current_sum = 0
            next_queue = []
            for node in queue:
                current_sum += node.val
                if node.left:
                    next_queue.append(node.left)
                if node.right:
                    next_queue.append(node.right)
            level_sum.append(current_sum)
            queue = next_queue
        
        # 第二次BFS：更新节点值
        queue = [root]
        root.val = 0  # 根节点没有表兄弟
        level = 0
        
        while queue:
            next_queue = []
            for node in queue:
                # 计算子节点的兄弟节点和
                sibling_sum = 0
                if node.left:
                    sibling_sum += node.left.val
                if node.right:
                    sibling_sum += node.right.val
                
                # 更新子节点值
                if node.left:
                    node.left.val = level_sum[level + 1] - sibling_sum
                    next_queue.append(node.left)
                if node.right:
                    node.right.val = level_sum[level + 1] - sibling_sum
                    next_queue.append(node.right)
            
            queue = next_queue
            level += 1
        
        return root

public class Solution {
    public TreeNode ReplaceValueInTree(TreeNode root) {
        if (root == null) return root;
        
        // 第一次BFS：计算每层的总和
        List<int> levelSum = new List<int>();
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        
        while (queue.Count > 0) {
            int size = queue.Count;
            int sum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.Dequeue();
                sum += node.val;
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            levelSum.Add(sum);
        }
        
        // 第二次BFS：更新节点值
        queue.Enqueue(root);
        root.val = 0; // 根节点没有表兄弟
        int level = 0;
        
        while (queue.Count > 0) {
            int size = queue.Count;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.Dequeue();
                
                // 计算子节点的兄弟节点和
                int siblingSum = 0;
                if (node.left != null) siblingSum += node.left.val;
                if (node.right != null) siblingSum += node.right.val;
                
                // 更新子节点值
                if (node.left != null) {
                    node.left.val = levelSum[level + 1] - siblingSum;
                    queue.Enqueue(node.left);
                }
                if (node.right != null) {
                    node.right.val = levelSum[level + 1] - siblingSum;
                    queue.Enqueue(node.right);
                }
            }
            level++;
        }
        
        return root;
    }
}

var replaceValueInTree = function(root) {
    if (!root) return root;
    
    // 第一次BFS：计算每层的总和
    const levelSum = [];
    let queue = [root];
    
    while (queue.length > 0) {
        let sum = 0;
        const nextQueue = [];
        for (const node of queue) {
            sum += node.val;
            if (node.left) nextQueue.push(node.left);
            if (node.right) nextQueue.push(node.right);
        }
        levelSum.push(sum);
        queue = nextQueue;
    }
    
    // 第二次BFS：更新节点值
    queue = [root];
    root.val = 0; // 根节点没有表兄弟
    let level = 0;
    
    while (queue.length > 0) {
        const nextQueue = [];
        for (const node of queue) {
            // 计算子节点的兄弟节点和
            let siblingSum = 0;
            if (node.left) siblingSum += node.left.val;
            if (node.right) siblingSum += node.right.val;
            
            // 更新子节点值
            if (node.left) {
                node.left.val = levelSum[level + 1] - siblingSum;
                nextQueue.push(node.left);
            }
            if (node.right) {
                node.right.val = levelSum[level + 1] - siblingSum;
                nextQueue.push(node.right);
            }
        }
        queue = nextQueue;
        level++;
    }
    
    return root;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历所有节点两次，每个节点的操作都是常数时间
空间复杂度O(n)队列最多存储一层的节点，最坏情况下为O(n)；levelSum数组存储每层和，最多O(log n)层

相关题目