586，BFS和DFS解层数最深叶子节点的和

Original 博哥数据结构和算法 2022-05-01

Even with two eyes, you only see half of the picture.

即便亲眼所见，也无法窥得全貌。

问题描述

来源：LeetCode第1302题

难度：中等

给你一棵二叉树的根节点root，请你返回层数最深的叶子节点的和。

示例 1:

输入：root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
输出：15

示例 2:

输入：root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]

输出：19

提示:

树中节点数目在范围 [1, 10^4] 之间。
1 <= Node.val <= 100

BFS解决

这题让求的是最深叶子节点的和，最容易想到的就BFS解决，也就是一层一层的从上往下遍历，BFS的遍历方式如下，也可以看下373，数据结构-6,树

到最后一层的时候我们再把节点的值相加即可。这里我们不知道哪一层是最深的层数，我们可以把每一层所有节点的值都相加，下一层会把上一次的给覆盖掉，最后一层下面没有了，所以没法覆盖，直接返回即可。来看下代码

public int deepestLeavesSum(TreeNode root) {
    //每层节点的和
    int res = 0;
    //队列
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    //队列不为空，继续访问队列的元素
    while (!queue.isEmpty()) {
        //当前层的节点数量
        int levelCount = queue.size();
        //当前层所有节点值的和
        res = 0;
        //遍历当前层的所有节点
        for (int j = 0; j < levelCount; j++) {
            TreeNode node = queue.poll();
            //累加当前层节点的值
            res += node.val;
            //如果左子节点不为空就把他加入到队列中
            if (node.left != null)
                queue.add(node.left);
            //如果右子节点不为空就把他加入到队列中
            if (node.right != null)
                queue.add(node.right);
        }
    }
    return res;
}

时间复杂度：O(N)，N是节点的个数，所有节点都要访问一遍

空间复杂度：O(N)，队列中存放的是每层节点的个数，满二叉树的时候最后一层节点的个数是（N+1）/2

DFS解决

这题除了BFS从上到下一层一层的访问以外，我们还可以使用DFS来解决，这里以前序遍历为例，往下遍历的时候需要计算节点的层数

如果当前节点的层数大于之前记录的最大层数，说明之前记录的层数还不是最大的，那之前累加的和sum肯定要作废，重新赋值为0，最大层数也要更新。
如果当前层数等于记录的最大层数，sum就累加。

来看下代码

//记录树的最大深度
private int maxLevel = 0;
//记录最后一层所有节点的和
private int sum = 0;

public int deepestLeavesSum(TreeNode root) {
    dfs(root, 0);
    return sum;
}

//level表示第几层，根节点是第0层
private void dfs(TreeNode root, int level) {
    //边界条件判断，如果是空直接返回
    if (root == null)
        return;
    //操作当前节点，如果没到最后一层，记录
    //当前访问过的最大层数，并且把sum重置为0，
    //也就是之前加的作废
    if (level > maxLevel) {
        maxLevel = level;
        sum = 0;
    }
    //如果到了最后一层，就把节点值相加
    if (level == maxLevel) {
        sum = sum + root.val;
    }
    //访问左子节点和右子节点，
    dfs(root.left, level + 1);
    dfs(root.right, level + 1);
}