1302. Deepest Leaves Sum

LeetCode medium original: C# #csharp #leetcode #medium #stack #tree #two-pointers

Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.

LeetCode Static

given корень бинарного дерева, вернуть сумму значений его самых глубоких листьев.

Exemple:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]

Output: 15

C# solution

correspondant/original

public class Solution {
    public int DeepestLeavesSum(TreeNode root) {
        int deepestSum = 0, depth = 0;
        var stack = new Stack<(TreeNode node, int depth)>();
        stack.Push((root, 0));
        while (stack.Count > 0) {
            var (node, currDepth) = stack.Pop();
            if (node.left == null && node.right == null) {
                if (depth < currDepth) {
                    deepestSum = node.val;
                    depth = currDepth;
                } else if (depth == currDepth) {
                    deepestSum += node.val;
                }
            } else {
                if (node.right != null) {
                    stack.Push((node.right, currDepth + 1));
                }
                if (node.left != null) {
                    stack.Push((node.left, currDepth + 1));
                }
            }
        }
        return deepestSum;
    }
}

C++ solution

brouillon automatique, à relire avant soumission

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int DeepestLeavesSum(TreeNode root) {
        int deepestSum = 0, depth = 0;
        var stack = new stack<(TreeNode node, int depth)>();
        stack.push((root, 0));
        while (stack.size() > 0) {
            var (node, currDepth) = stack.pop();
            if (node.left == null && node.right == null) {
                if (depth < currDepth) {
                    deepestSum = node.val;
                    depth = currDepth;
                } else if (depth == currDepth) {
                    deepestSum += node.val;
                }
            } else {
                if (node.right != null) {
                    stack.push((node.right, currDepth + 1));
                }
                if (node.left != null) {
                    stack.push((node.left, currDepth + 1));
                }
            }
        }
        return deepestSum;
    }
}

Java solution

brouillon automatique, à relire avant soumission

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int DeepestLeavesSum(TreeNode root) {
        int deepestSum = 0, depth = 0;
        var stack = new Stack<(TreeNode node, int depth)>();
        stack.push((root, 0));
        while (stack.size() > 0) {
            var (node, currDepth) = stack.pop();
            if (node.left == null && node.right == null) {
                if (depth < currDepth) {
                    deepestSum = node.val;
                    depth = currDepth;
                } else if (depth == currDepth) {
                    deepestSum += node.val;
                }
            } else {
                if (node.right != null) {
                    stack.push((node.right, currDepth + 1));
                }
                if (node.left != null) {
                    stack.push((node.left, currDepth + 1));
                }
            }
        }
        return deepestSum;
    }
}

Python solution

correspondant/original

class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        deepest_sum = 0
        depth = 0
        stack = [(root, 0)]
        
        while stack:
            node, curr_depth = stack.pop()
            
            if not node.left and not node.right:
                if depth < curr_depth:
                    deepest_sum = node.val
                    depth = curr_depth
                elif depth == curr_depth:
                    deepest_sum += node.val
            else:
                if node.right:
                    stack.append((node.right, curr_depth + 1))
                if node.left:
                    stack.append((node.left, curr_depth + 1))
        
        return deepest_sum

Go solution

correspondant/original

package main

func deepestLeavesSum(root *TreeNode) int {
    deepestSum, depth := 0, 0
    stack := [][2]interface{}{{root, 0}}

    for len(stack) > 0 {
        node, currDepth := stack[len(stack)-1][0].(*TreeNode), stack[len(stack)-1][1].(int)
        stack = stack[:len(stack)-1]

        if node.Left == nil && node.Right == nil {
            if depth < currDepth {
                deepestSum = node.Val
                depth = currDepth
            } else if depth == currDepth {
                deepestSum += node.Val
            }
        } else {
            if node.Right != nil {
                stack = append(stack, [2]interface{}{node.Right, currDepth + 1})
            }
            if node.Left != nil {
                stack = append(stack, [2]interface{}{node.Left, currDepth + 1})
            }
        }
    }
    return deepestSum
}

Algorithm

Поместите корень в стек.

Пока стек не пуст. Извлеките узел из стека и обновите текущее number. Если узел является листом, обновите сумму самых глубоких листьев deepest_sum. Поместите правый и левый дочерние узлы в стек.

return deepest_sum.

😎

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres

Il n'y a pas encore d'offres actives.