1302. Deepest Leaves Sum

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;
    }
}

#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;
    }
}

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;
    }
}

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

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

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

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

Верните deepest_sum.

😎