thảo luận Leetcode mỗi ngày

use std::rc::Rc;
use std::cell::RefCell;

type Node = Rc<RefCell<TreeNode>>;

impl Solution {
    pub fn kth_largest_level_sum(root: Option<Node>, k: i32) -> i64 {
        let mut level_sums = vec![0; 10usize.pow(5)];
        let k = k as usize;

        fn dfs(node: Option<Node>, level_sums: &mut [i64], level: usize) -> usize {
            match node {
                Some(node) => {
                    let node = node.borrow();

                    level_sums[level] += node.val as i64;

                    let left = node.left.as_ref().map(|left| left.clone());
                    let right = node.right.as_ref().map(|right| right.clone());

                    let left_level = dfs(left, level_sums, level + 1);
                    let right_level = dfs(right, level_sums, level + 1);

                    left_level.max(right_level)
                },
                None => level
            }
        }

        let max_level = dfs(root, &mut level_sums, 0);

        if max_level < k {
            return -1;
        }

        level_sums.select_nth_unstable_by(k - 1, |a, b| b.cmp(a));
        level_sums[k - 1]
    }
}

class Solution {
    Map<Integer, Long> map = new HashMap<>();

    public long kthLargestLevelSum(TreeNode root, int k) {
        travel(root, 0);
        List<Long> list = new ArrayList<>(map.values());
        Collections.sort(list);

        if (k > list.size())
            return -1L;

        return list.get(list.size() - k);
    }

    void travel(TreeNode node, int level) {
        if (node == null)
            return;;
        
        map.put(level, map.getOrDefault(level, 0L) + node.val);
        travel(node.left, level + 1);
        travel(node.right, level + 1);
    }
}

class Solution:
    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        sumOfLevel = []
        q = deque([root])
        sumSiblingNode = {}

        while q:
            n = len(q)
            sumOfLevel.append(0)
            for _ in range(n):
                node = q.popleft()
                if node != None:
                    sumOfLevel[-1] += node.val
                    q.append(node.left)
                    q.append(node.right)
                    sumSibling = 0 if node.left is None else node.left.val
                    sumSibling += 0 if node.right is None else node.right.val
                    if node.left != None:
                        sumSiblingNode[node.left] = sumSibling
                    if node.right != None:
                        sumSiblingNode[node.right] = sumSibling
        
        sumSiblingNode[root] = root.val
        q = deque([root])
        level = 0
        while q:
            n = len(q)
            for _ in range(n):
                node = q.popleft()
                if node != None:
                    node.val = sumOfLevel[level] - sumSiblingNode[node]
                    q.append(node.left)
                    q.append(node.right)
            level += 1
        return root

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        queue = deque()
        queue.append((ListNode(-1), root))
        while queue:
            size = len(queue)
            parentSum = defaultdict(int)
            levelSum = 0
            nodes = []
            for _ in range(size):
                parent, node = queue.popleft()
                parentSum[parent] += node.val
                levelSum += node.val
                nodes.append((parent, node))
                if node.left != None:
                    queue.append((node, node.left))

                if node.right != None:
                    queue.append((node, node.right))

            for parent, node in nodes:
                node.val = levelSum - parentSum[parent]

        return root

class Solution {

    /**
     * @param TreeNode $root
     * @param Integer $k
     * @return Integer
     */
    function kthLargestLevelSum($root, $k) {
        $sum = [];
        $level = -1;
        $this->getLevelSum($root, $level, $sum);
        rsort($sum);
        
        return isset($sum[$k-1]) ? $sum[$k-1] : -1;
    }

    /**
     * @param TreeNode $root
     * @param Integer $level
     * @param Array $sum
     */
    function getLevelSum($root, $level, &$sum,) {
        if (!$root) return;

        $level++;
        if (!isset($sum[$level])) $sum[$level] = 0;

        $sum[$level] += $root->val;
        $this->getLevelSum($root->left, $level, $sum);
        $this->getLevelSum($root->right, $level, $sum);
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        queue = deque()
        root.val = 0
        queue.append(root)
        currentLevelSum = 0
        while queue:
            size = len(queue)
            nextLevelSum = 0
            for _ in range(size):
                node = queue.popleft()
                node.val += currentLevelSum

                leftVal = node.left.val if node.left != None else 0
                rightVal = node.right.val if node.right != None else 0
                if node.left != None:
                    nextLevelSum += node.left.val
                    node.left.val = - (leftVal + rightVal)
                    queue.append(node.left)

                if node.right != None:
                    nextLevelSum += node.right.val
                    node.right.val = - (leftVal + rightVal)
                    queue.append(node.right)

            currentLevelSum = nextLevelSum

        return root