2641. Cousins in Binary Tree II

MediumView on LeetCode

Hash Table Tree Depth-First Search Breadth-First Search Binary Tree

Time: O(n)

Space: O(n)

Intuition

Replace each node value with sum of cousin values. BFS: track level sum and parent-child sums.

Algorithm

1BFS. For each node: cousin_sum = level_sum - (node.left?.val + node.right?.val of parent).
2Two-pass BFS: first pass compute level sums and sibling sums. Second pass assign cousin sums.

Common Pitfalls

•Cousin nodes are at same depth but different parents. Sum all same-depth values, subtract sibling pair.

2641.cs


// Approach: BFS to compute level sums; replace each node with levelSum minus sum of siblings' subtrees.
// Time: O(n) Space: O(n)

// Definition for a binary tree node.
public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution
{
    public TreeNode ReplaceValueInTree(TreeNode root)
    {
        var map = new Dictionary<int, int>();
        DFS(root, 0, map);
        DFS2(root, 0, 0, map);

        return root;
    }

    void DFS(TreeNode root, int level, Dictionary<int, int> map)
    {
        if (root == null)
            return;

        if (map.ContainsKey(level))
            map[level] += root.val;
        else
            map.Add(level, root.val);

        DFS(root.left, level + 1, map);
        DFS(root.right, level + 1, map);
    }

    void DFS2(TreeNode root, int sibling, int level, Dictionary<int, int> map)
    {
        if (root == null)
            return;

        root.val = map[level] - root.val - sibling;
        int lv = root.left != null ? root.left.val : 0;
        int rv = root.right != null ? root.right.val : 0;

        DFS2(root.left, rv, level + 1, map);
        DFS2(root.right, lv, level + 1, map);
    }
}

Was this solution helpful?