LeetCode 1302. Deepest Leaves Sum    原题链接    中等

作者： 作者的头像   wzc1995 ,  2020-01-01 09:41:42 ,  所有人可见 ,  阅读 1365

8


题目描述

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

样例

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

限制

  • 树中节点数目在 1 到 10^4 之间。
  • 每个节点的值在 1 到 100 之间。

算法

(深度优先遍历 / DFS) $O(n)$
  1. 深度优先遍历，函数的参数记录当前的高度。
  2. 维护两个全局变量，当前的最深的高度 maxDepth，以及在最深高度的和 sum。
  3. 遍历时，如果当前高度大于 maxDepth，则更新 sum 为当前结点的值。如果当前高度等于 maxDepth，则 sum 累计上当前结点的值。

时间复杂度

  • 每个结点仅遍历一次，故时间复杂度为 $O(n)$。

空间复杂度

  • 递归需要系统的栈空间，额外需要 $O(h)$ 的空间，其中 $h$ 为最深高度。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void solve(TreeNode *r, int depth, int &maxDepth, int &sum) {
        if (!r)
            return;
        if (depth > maxDepth) {
            maxDepth = depth;
            sum = r -> val;
        } else if (depth == maxDepth) {
            sum += r -> val;
        }

        solve(r -> left, depth + 1, maxDepth, sum);
        solve(r -> right, depth + 1, maxDepth, sum);
    }

    int deepestLeavesSum(TreeNode* root) {
        int maxDepth = 0, sum = 0;
        solve(root, 1, maxDepth, sum);
        return sum;
    }
};

2 评论

用户头像
szh_2003   2022-08-18 01:04         踩      回复

## 这是BFS版本的题解

TreeNode* q[10010];
class Solution {
public:
    int deepestLeavesSum(TreeNode* root) {
        return bfs(root);
    }
    int bfs(TreeNode* node) {
        int res = 0;
        int hh = 0, tt = 0;
        q[0] = node;
        while(hh <= tt) {
            res = 0;
            int cnt = tt - hh + 1;
            for(int i = 1; i <= cnt; i++) {
                TreeNode* t = q[hh++];
                res += t->val;
                if(t->left != nullptr) q[++tt] = t->left;
                if(t->right != nullptr) q[++tt] = t->right;
            }
        }
        return res;
    }
};
用户头像
szh_2003   2022-08-18 01:06         踩      回复

或者这样

class Solution {
public:
    int deepestLeavesSum(TreeNode* root) {
        int res = 0;
        queue<TreeNode*> q;
        q.push(root);
        while(q.size()) {
            int cnt = q.size();
            res = 0;
            for(int i = 1; i <= cnt; i++) {
                TreeNode* node = q.front();
                q.pop();
                res += node->val;
                if(node->left != nullptr) q.push(node->left);
                if(node->right != nullptr) q.push(node->right);
            }
        }
        return res;
    }
};