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

class Solution {
    List<Integer> list = new ArrayList<>();

    public TreeNode replaceValueInTree(TreeNode root) {
        travelSum(root, 0);
        travel(root, 0, list.get(0));
        return root;
    }

    void travel(TreeNode node, int level, int sub) {
        if (node == null)
            return;

        node.val = list.get(level) - sub;
        sub = 0;

        if (node.left != null)
            sub += node.left.val;

        if (node.right != null)
            sub += node.right.val;

        travel(node.left, level + 1, sub);
        travel(node.right, level + 1, sub);
    }

    void travelSum(TreeNode node, int level) {
        if (node == null)
            return;

        if (level == list.size())
            list.add(0);

        list.set(level, list.get(level) + node.val);
        travelSum(node.left, level + 1);
        travelSum(node.right, level + 1);
    }
}

class Solution {
public:
    TreeNode* replaceValueInTree(TreeNode* root) {
        
        queue<vector<TreeNode*>> q;
        vector<TreeNode*> first;
        first.push_back(root);
        q.push(first);

        while (!q.empty()) {
            int n = q.size();
            int totalSum = 0;
            vector<int> partSum;
            vector<vector<TreeNode*>> vt;

            for (int i = 0; i < n; i++) {
                vector<TreeNode*> tmp = q.front();
                q.pop();
                int sum = 0;
                for (int i = 0; i < tmp.size(); i++) {
                    sum += tmp[i]->val;
                    vector<TreeNode*> a;
                    if (tmp[i]->right != nullptr) a.push_back(tmp[i]->right);
                    if (tmp[i]->left != nullptr) a.push_back(tmp[i]->left);
                    q.push(a);
                }
                totalSum += sum;
                partSum.push_back(sum);
                vt.push_back(tmp);
            }

            for (int i = 0; i < vt.size(); i++) {
                for (int j = 0; j < vt[i].size(); j++) {
                    vt[i][j]->val = totalSum - partSum[i];
                }
            }
        }

        return root;
    }
};

class Solution {
public:
    TreeNode* replaceValueInTree(TreeNode* root) {
        queue<TreeNode*> q,q2;
        q.push(root);
        root->val = 0;
        int len;
        TreeNode* node;
        long long sum;
        int val;
        while (!q.empty()) {
            q2 = q;
            sum = 0;
            len = q.size();
            for (int i = 0; i < len; ++i) {
                node = q.front();
                q.pop();
                val = (node->left ? node->left->val : 0) + (node->right ? node->right->val : 0);
                sum += val;
                if (node->left) {
                    node->left->val = val;                   
                }
                if (node->right) {
                    node->right->val = val;                   
                }
            }
            while (!q2.empty()) {
                node = q2.front();
                q2.pop();
                if (node->left) {
                    node->left->val = sum - node->left->val;
                    q.push(node->left);
                }
                if (node->right) {
                    node->right->val = sum - node->right->val;
                    q.push(node->right);
                }
            }
        }
        return root;
    }
};

class Solution {
    public TreeNode replaceValueInTree(TreeNode root) {
        List<Integer> sum_level = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            int sum =0;
            TreeNode node = new TreeNode();
            for(int i = 0 ; i < size;i++){
                node = queue.poll();
                sum+= node.val;
                if(node.left!=null) queue.add(node.left);
                if(node.right!=null) queue.add(node.right);
            }
            sum_level.add(sum);
        }
        TreeNode dummy = new TreeNode(-1);
        dummy.left = root;
        TreeNode curNode = new TreeNode(-1);
        buildTree(curNode,dummy,0,sum_level);
        return curNode.left;
    }
    public void buildTree(TreeNode curNode, TreeNode parrent, int level, List<Integer> sum_level){
        if(level>=sum_level.size()) return;
        int sum = sum_level.get(level);
        //System.out.println(parrent.val);
        if(parrent.left!=null) {
            sum-=parrent.left.val;
        }
        if(parrent.right!=null) {
            sum-=parrent.right.val;
        }
        if(parrent.left!=null){
            TreeNode left = new TreeNode(sum);
            curNode.left = left;
            buildTree(left, parrent.left, level+1, sum_level);
        }
        if(parrent.right!=null){
            TreeNode right = new TreeNode(sum);
            curNode.right = right;
            buildTree(right, parrent.right, level+1, sum_level);
        }       
    }
}

    public TreeNode replaceValueInTree(TreeNode root) {
        List<Integer> levelSum = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()) {
            int sum = 0;
            int size = q.size();
            while(size > 0) {
                TreeNode tree = q.poll();
                sum += tree.val;
                if(tree.left != null) {
                    q.offer(tree.left);
                }
                if(tree.right != null) {
                    q.offer(tree.right);
                }
                size--;
            }
            levelSum.add(sum);
        }
        root.val = 0;
        q.offer(root);
        int level = 0;
        while(!q.isEmpty() && level < levelSum.size() - 1) {
            int size = q.size();
            while(size > 0) {
                int sum = 0;
                TreeNode tree = q.poll();
                if(tree.left != null) {
                    q.offer(tree.left);
                    sum += tree.left.val;
                }
                if(tree.right != null) {
                    q.offer(tree.right);
                    sum += tree.right.val;
                }
                if(tree.left != null) {
                    tree.left.val = levelSum.get(level + 1) - sum;
                }
                if(tree.right != null) {
                    tree.right.val = levelSum.get(level + 1) - sum;
                }
                size--;
            }
            level++;
        }
        return root;
    }

class Solution:
    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        queue = deque()
        queue.append([root, 0]) # node, sibling val
        layerSum = root.val

        while queue:
            lenQ = len(queue)
            currSum = 0

            for _ in range(lenQ):
                node, nextNodeVal = queue.popleft()
                node.val = layerSum - node.val - nextNodeVal

                if node.left:
                    nextNodeVal = 0
                    if node.right:
                        nextNodeVal = node.right.val
                    queue.append([node.left, nextNodeVal])
                    currSum += node.left.val
                if node.right:
                    nextNodeVal = 0
                    if node.left:
                        nextNodeVal = node.left.val
                    queue.append([node.right, nextNodeVal])
                    currSum += node.right.val
               
            layerSum = currSum

        return root

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode replaceValueInTree(TreeNode root) {
        if (root == null) return root;
        Queue<TreeNode> queue = new ArrayDeque<>();
        List<Integer> sums = new ArrayList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int sum = 0;
            int size = queue.size();
            while (size-- > 0) {
                TreeNode curr = queue.poll();
                sum += curr.val;
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
            }
            sums.add(sum);
        }
        queue.offer(root);
        root.val = 0;
        int i = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                TreeNode curr = queue.poll();
                int cousinSum = (curr.left != null ? curr.left.val : 0) + (curr.right != null ? curr.right.val : 0);
                if (curr.left != null) {
                    curr.left.val = sums.get(i) - cousinSum;
                    queue.offer(curr.left);
                }
                if (curr.right != null) {
                    curr.right.val = sums.get(i) - cousinSum;
                    queue.offer(curr.right);
                }
            }
            i++;
        }
        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 add (self, nodes: list):
        sum = 0
        index_sum = []
        for idx, node in enumerate(nodes):
            i_sum = 0
            if node.left:
                i_sum += node.left.val
            if node.right:
                i_sum += node.right.val
            index_sum.append(i_sum)
            sum += i_sum
        return sum, index_sum

    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        it = root
        it.val = 0 # root node always 0
        current_nodes = [it]
        next_nodes = []
        while current_nodes:
            sum, idx_sum = self.add(current_nodes)
            for idx, node in enumerate(current_nodes):
                if node.left:
                    node.left.val = sum - idx_sum[idx]
                    next_nodes.append(node.left)
                if node.right:
                    node.right.val = sum - idx_sum[idx]
                    next_nodes.append(node.right)
            current_nodes = next_nodes
            next_nodes = []
        return root

class Solution {
    func replaceValueInTree(_ root: TreeNode?) -> TreeNode? {
        guard let root else { return nil }
        root.val = 0
        var trees = [root]
        var sum = (root.left?.val ?? 0) + (root.right?.val ?? 0)
        func bfs() {
            guard trees.count > 0 else { return }
            var newTrees:[TreeNode] = []
            var newSum = 0
            func addNewNode(node: TreeNode?, val: Int) {
                if let node = node {
                    node.val = val
                    newTrees.append(node)
                    newSum += (node.left?.val ?? 0) + (node.right?.val ?? 0)
                }
            }
            for tree in trees {
                let newVal = sum - (tree.right?.val ?? 0) - (tree.left?.val ?? 0)
                addNewNode(node: tree.left, val: newVal)
                addNewNode(node: tree.right, val: newVal)
            }
            trees = newTrees
            sum = newSum
            bfs()
        }
        bfs()
        return root
    }
}

function replaceValueInTree(root: TreeNode | null): TreeNode | null {
    if (!root) return null;
    const q: TreeNode[] = [root];
    
    while (q.length) {
        const size = q.length;
        let sum = 0;
        for (let i = 0; i < size; i++) {
            const node = q[i];
            sum += node ? node.val : 0;
        }
        for (let i = 0; i < size; i += 2) {
            const l = q.shift(), r = q.shift();
            const a = l?.val || 0, b = r?.val || 0;
            if (l) {
                l.val = sum - a - b;
                q.push(l.left);
                q.push(l.right);
            }
            if (r) {
                r.val = sum - a - b;
                q.push(r.left);
                q.push(r.right);
            }
        }
    }

    return root;
}

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

type Node = Rc<RefCell<TreeNode>>;

impl Solution {
    pub fn replace_value_in_tree(mut root: Option<Node>) -> Option<Node> {
        fn sum_levels(node: Option<Node>, level: usize, level_sums: &mut [i32]) {
            match node {
                Some(mut node) => {
                    let mut node = node.borrow_mut();

                    level_sums[level] += node.val;

                    let mut children_sum = 0;

                    let left =
                        node.left.as_ref().map(|left| {
                            children_sum += left.borrow().val;
 
                            left.clone()
                        });

                    let right =
                        node.right.as_ref().map(|right| {
                            children_sum += right.borrow().val;

                            right.clone()
                        });

                    if left.is_some() {
                        sum_levels(left, level + 1, level_sums);
                    }

                    if right.is_some() {
                        sum_levels(right, level + 1, level_sums);
                    }

                    node.val = children_sum;
                },
                None => ()
            }
        }

        fn modify_tree(node: Option<Node>, children_sum: i32, level: usize, level_sums: &[i32]) {
            match node {
                Some(mut node) => {
                    let mut node = node.borrow_mut();

                    let next_children_sum = node.val;
                    node.val = level_sums[level] - children_sum;

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

                    if left.is_some() {
                        modify_tree(left, next_children_sum, level + 1, level_sums);
                    }

                    if right.is_some() {
                        modify_tree(right, next_children_sum, level + 1, level_sums);
                    }
                },
                None => ()
            }
        }

        let mut level_sums = vec![0; 10usize.pow(5)];
        sum_levels(root.as_ref().map(|root| root.clone()), 0, &mut level_sums);

        modify_tree(root.as_ref().map(|root| root.clone()), 0, 0, &level_sums);

        root.as_mut().map(|mut root| root.borrow_mut().val = 0);

        root
    }
}

class Pair {
    TreeNode node;
    int parentSum;

    public Pair(TreeNode node, int parentSum) {
        this.node = node;
        this.parentSum = parentSum;
    }
}
class Solution {
    public TreeNode replaceValueInTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        root.val = 0;
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            int total = 0;
            List<Pair> nextNodes = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                int parentSum = 0;
                TreeNode curr = queue.poll();
                parentSum += curr.left == null ? 0 : curr.left.val;
                parentSum += curr.right == null ? 0 : curr.right.val;
                total += parentSum;

                if (curr.left != null) {
                    nextNodes.add(new Pair(curr.left, parentSum));
                }
                if (curr.right != null) {
                    nextNodes.add(new Pair(curr.right, parentSum));
                }
            }

            for (Pair pair : nextNodes) {
                pair.node.val = total - pair.parentSum;
                queue.offer(pair.node);
            }
        }

        return root;
    }
}