【二叉树】层数最深叶子节点的和

题目描述

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

示例1

输入：root = [1,2,5,7,0,null,null]
输出：7

解题思路 

这道题正向思路是每一层都做一次计算，直到等到最后一层的结果；

TreeNode参考代码如下：

package org.example;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

按照这个思路：

• 第一层，结果为1；
• 第二层，结果为7；
• 第三层，结果也为7；
• 返回最后一层结果；

为了能解决上述问题，我使用了队列（java中的Deque），代码实现如下：

import org.example.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

public class Solution3 {
    
    public int deepestLeavesSum(TreeNode root) {

        Deque<TreeNode> deque = new LinkedList<>();
        if (root != null) {
            deque.offer(root);
        }

        int sum = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            sum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.poll();
                sum += node.val;
                if (node.left != null) {
                    deque.offer(node.left);
                }
                if (node.right != null) {
                    deque.offer(node.right);
                }
            }
        }
        return sum;
    }


    public static void main(String[] args) {
        Solution3 solution = new Solution3();

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.left.left.left = new TreeNode(7);
        root.right.right = new TreeNode(6);
        root.right.right.right = new TreeNode(8);

        System.out.println(solution.deepestLeavesSum(root));

    }
}

为了能够提升效率，这里我使用dfs做改造，完全使用递归核心逻辑：

• 如果节点为null，直接返回；
• 如果节点所在层数大于最大层数，则让最大层数加一，同时将结果设置成0；
• 如果节点所在层数等于最大层数，则做加法，结果加上根节点的value；
• 然后递归调用代码；

具体代码实现如下：

import org.example.TreeNode;

public class Solution {

    int maxLevel = 0;
    int res = 0;

    public int deepestLeavesSum(TreeNode root) {

        dfs(root, 0);
        return res;
    }

    private void dfs(TreeNode root, int level) {
        if (root == null) {
            return;
        }

        if (maxLevel < level) {
            maxLevel = level;
            res = 0;
        }

        if (level == maxLevel) {
            res += root.val;
        }

        dfs(root.left, level + 1);
        dfs(root.right, level + 1);
    }


    public static void main(String[] args) {
        Solution solution = new Solution();

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.left.left.left = new TreeNode(7);
        root.right.right = new TreeNode(6);
        root.right.right.right = new TreeNode(8);

        System.out.println(solution.deepestLeavesSum(root));

    }

 这个是2代码实现的耗时差别，1ms的使用dfs，6ms的是最初的解决思路。

总结

这道题是一道中等难度的二叉树遍历的题目，如果对二叉树DFS和BFS都比较清楚，能快速的解决这个问题。如果有更快、更简洁的代码实现欢迎回复。