1302. Deepest Leaves Sum

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

Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.

LeetCode Static

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

Ví dụ:

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

Output: 15

C# lời giải

đã khớp/gốc

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++ lời giải

bản nháp tự động, xem lại trước khi gửi

#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 lời giải

bản nháp tự động, xem lại trước khi gửi

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 lời giải

đã khớp/gốc

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 lời giải

đã khớp/gốc

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

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm

Chưa có việc làm đang hoạt động.