【LeetCode】1302. Deepest Leaves Sum

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

Example 1:

image.png

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.

【Idea】
BFS 队列or递归, 参数中增加一个cur_height,在每次遍历节点时做一次height比较来绝对是否更新result_sum

【Solution】

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        # 这里写global, 或者定义一个__init__函数
        global deepest, result
        deepest, height, result = -1, 1, 0

        def sub(root, height):
            global deepest, result
            if not root:
                return 
            if height == deepest:
                result += root.val 
            elif height > deepest:
                deepest = height
                result = root.val 

            sub(root.left, height+1)
            sub(root.right, height+1)

        if not root:
            return 0       
        sub(root, height)
        return result
        
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。