acwing2022秋招每日一题 1302. 层数最深叶子节点的和

题目

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

思路

根据层序遍历，访问所有节点。将每一层上的结点，进行统计，直到最后一层时，统计所有节点数。

解法

class Solution {
public:
    int levelTravel(TreeNode *root, queue<TreeNode *> &q)
    {
        q.push(root);
        int res = 0;

        while (!q.empty())
        {
            int len = q.size();
            res = 0;
            while (len--)
            {
                TreeNode *n;
                n = q.front();
                res += n->val;
                if (n->left)
                {
                    q.push(n->left);
                }
                if (n->right)
                {
                    q.push(n->right);
                }
                q.pop();
            }
        }
        return res;
    }

    int findDeepth(TreeNode *root)
    {
        int deepth = 1;
        TreeNode *head = root;
        while (head->left)
        {
            head = head->left;
            deepth += 1;
        }
        return deepth;
    }

    int deepestLeavesSum(TreeNode *root)
    {
        int res = 0;
        int level = 0;
        queue<TreeNode *> q;
        res = levelTravel(root, q);
        int depth = findDeepth(root);
        return res;
    }
};

yxc解法

class Solution {
public:
    int depth = -1, sum = 0;

    void dfs(TreeNode* root, int d) {
        if (!root) return;
        if (d > depth) depth = d, sum = root->val;
        else if (d == depth) sum += root->val;
        dfs(root->left, d + 1);
        dfs(root->right, d + 1);
    }

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

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/4111095/

解法分析

广度优先算法，访问所有节点，每进一步意味着深入一层。