LeetCode Ts-2641. Cousins in Binary Tree II

    AllenLi
    CodingLeetCode Js-Tree

    Given the root of a binary tree, replace the value of each node in the tree with the sum of all its cousins’ values.
    Two nodes of a binary tree are cousins if they have the same depth with different parents.
    Return the root of the modified tree.
    Note that the depth of a node is the number of edges in the path from the root node to it.

    給予一個二元樹的根節點，將樹中每個節點的值替換為所有同層節點的值總和。
二元樹中的兩個節點如果深度相同且富節點不同，則他們叫做同層節點。
回傳修改後的樹根節點。
請注意，節點的深度是指從跟節點到該節點的路徑上邊的數量。

    Example 1:

    Input: root = [5,4,9,1,10,null,7]
Output: [0,0,0,7,7,null,11]
Explanation: The diagram above shows the initial binary tree and the binary tree after changing the value of each node.
- Node with value 5 does not have any cousins so its sum is 0.
- Node with value 4 does not have any cousins so its sum is 0.
- Node with value 9 does not have any cousins so its sum is 0.
- Node with value 1 has a cousin with value 7 so its sum is 7.
- Node with value 10 has a cousin with value 7 so its sum is 7.
- Node with value 7 has cousins with values 1 and 10 so its sum is 11.

    Example 2:

    Input: root = [3,1,2]
Output: [0,0,0]
Explanation: The diagram above shows the initial binary tree and the binary tree after changing the value of each node.
- Node with value 3 does not have any cousins so its sum is 0.
- Node with value 1 does not have any cousins so its sum is 0.
- Node with value 2 does not have any cousins so its sum is 0.

    Solution:
    一開始先確認 root 是否存在，若不存在直接回傳，
    而當根節點沒有同層的 cousins，因此將其值設為 0。
    接著使用 queue 進行 BFS，每次迭代處理一層的節點：
    先遍歷當層節點，計算下一層所有子節點的總和 levelSum，並將子節點加入 next。
    之後再根據公式：newValue = levelSum – siblingSum，更新下一層節點的值。
    最後持續迭代直到整棵樹處理完成。

    Code 1: BigO(n)

    /**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function replaceValueInTree(root: TreeNode | null): TreeNode | null {
    if (!root) return null;
    root.val = 0;
    let queue: TreeNode[] = [root];

    while (queue.length) {
        const next: TreeNode[] = [];
        let levelSum = 0;
        for (const node of queue) {
            if (node.left) {
                levelSum += node.left.val;
                next.push(node.left);
            }
            if (node.right) {
                levelSum += node.right.val;
                next.push(node.right);
            }
        }

        for (const node of queue) {
            const siblingSum: number = (node.left?.val ?? 0) + (node.right?.val ?? 0);
            if (node.left) node.left.val = levelSum - siblingSum;
            if (node.right) node.right.val = levelSum - siblingSum;
        }
        queue = next;
    }
    return root;
};

    FlowChart:
    Example 1

    Input: root = [5,4,9,1,10,null,7]

Next-level original values: [ 4, 9 ]
LevelSum: 13
Next-level updated values: [ 0, 0 ]
Next-level original values: [ 1, 10, 7 ]
LevelSum: 18
Next-level updated values: [ 7, 7, 11 ]
Next-level original values: []
LevelSum: 0
Next-level updated values: []

return root; // [0,0,0,7,7,null,11]

    Example 2

    Input: root = [3,1,2]

Next-level original values: [ 1, 2 ]
LevelSum: 3
Next-level updated values: [ 0, 0 ]
Next-level original values: []
LevelSum: 0
Next-level updated values: []

return root; // [0,0,0]

    Related Posts