4

LeetCode: 1302. Deepest Leaves Sum

 3 years ago
source link: https://mozillazg.com/2020/12/leetcode-1302-deepest-leaves-sum.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

题目

原题地址：https://leetcode.com/problems/deepest-leaves-sum/

Given a binary tree, return the sum of values of its deepest leaves.

Example 1:

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

Constraints:

  • The number of nodes in the tree is between 1 and 10^4.
  • The value of nodes is between 1 and 100.

解法

通过前序遍历寻找最深的节点，然后将他们的值相加，可以在寻找节点的过程中做相加操作。

这个方法的 Python 代码类似下面这样:

# 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 deepestLeavesSum(self, root: TreeNode) -> int:
        self._max_depth = 0
        self._sum = 0
        self._preorder(root, 0)

        return self._sum

    def _preorder(self, root, current_deepth):
        if root is None:
            return

        # 将最深的节点值详见
        if current_deepth == self._max_depth:
            self._sum += root.val

        # 发现更深的节点，更新 max_depth 信息同时重置 sum 的值
        if current_deepth > self._max_depth:
            self._max_depth = current_deepth
            self._sum = root.val

        self._preorder(root.left, current_deepth + 1)
        self._preorder(root.right, current_deepth + 1)

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK