1302. 层数最深叶子节点的和

https://leetcode-cn.com/problems/deepest-leaves-sum/

Java

/*
 * @Author: Goog Tech
 * @Date: 2020-09-11 15:42:07
 * @LastEditTime: 2020-09-11 15:42:32
 * @Description: https://leetcode-cn.com/problems/deepest-leaves-sum/
 * @FilePath: \leetcode-googtech\#1302. Deepest Leaves Sum\Solution.java
 * @WebSite: https://algorithm.show/
 */

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {

    // 解题思路: 利用辅助队列进行深度优先搜索,每次将上一次结果清零. 解题步骤如下所示:
    // 1. 一层层地遍历二叉树中的节点,将其逐个存储到 queue 中,并计算出每层节点之和
    // 2. 若还有下一层,则将存储在辅助队列中的上层节点全部清零
    // 3. 最后一次遍历后所得到的 sum 既是最深叶子节点的和
    public int deepestLeavesSum(TreeNode root) {
        // 判断根节点是否为空
        if(root == null) return 0;
        // 初始化辅助队列,其用于存储二叉树中每层的节点
        Queue<TreeNode> queue = new LinkedList<>();
        // 将根节点入队
        queue.offer(root);
        // 初始化最深叶子节点的和
        int sum = 0;
        // 判断当前辅助队列,即二叉树的下一层是否为空
        while(!queue.isEmpty()) {
            // 若二叉树还有下一层,则重新初始化最深叶子节点的和
            sum = 0;
            // 遍历存储在队列中的上层节点,并将其逐个出队
            for(int i = queue.size(); i > 0; i--) {
                TreeNode currentNode  = queue.poll();
                // 记录当前层节点的和
                sum += currentNode.val;
                // 将下一层节点入队
                if(currentNode.left != null) queue.offer(currentNode.left);
                if(currentNode.right != null) queue.offer(currentNode.right);
            }
        }
        // 返回最深叶子节点的和
        return sum;
    }
}

Python

'''
Author: Goog Tech
Date: 2020-09-11 15:42:12
LastEditTime: 2020-09-11 15:42:48
Description: https://leetcode-cn.com/problems/deepest-leaves-sum/
FilePath: \leetcode-googtech\#1302. Deepest Leaves Sum\Solution.py
WebSite: https://algorithm.show/
'''

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

class Solution(object):

    # 维护两个全局变量 maxDepth 和 total
    # maxDepth 用于记录搜索到的节点的最大深度值, total 则用于记录层数最深的叶子节点的和
    def __init__(self):
        self.total = 0
        self.maxDepth = -1

    # 深度优先遍历
    # 从根节点开始进行搜索,在搜索的同时记录当前节点的深度
    def deepestLeavesSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def dfs(node, depth):
            # 判断当前节点是否为空
            if not node: return
            # 若当前节点的深度 depth 大于 maxDepth,则重新对两个全局变量进行初始化
            if depth > self.maxDepth:
                self.maxDepth, self.total = depth, node.val
            # 若等于则将当前叶子节点 node 的权值累加到 total 中 
            # 若小于则忽略,进而继续进行深度搜索
            elif depth == self.maxDepth:
                self.total += node.val
            # 对当前节点的左右子树继续进行深度遍历
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)
        # 传入二叉树的根节点及初始深度值
        dfs(root, 0)
        # DFS 结束后,深度最大的叶子节点的权值之和即存储在 total 中
        return self.total