小鲸鱼的梦境
0%

『LeetCode』1302 层数最深叶子节点的和

发表于 分类于 Valine：
本文字数： 2.6k 阅读时长 ≈ 2 分钟

题目

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

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

示例 1：

pic

输入：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

统计最深层叶子节点的值的和，层序遍历是很基本的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Code language: Python
class Solution:
    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        st = deque()
        if root:
            st.append(root)
        cnt = 0
        while st:
            cnt = 0
            for _ in range(len(st)):
                cur = st.popleft()
                cnt += cur.val
                if cur.left:
                    st.append(cur.left)
                if cur.right:
                    st.append(cur.right)
        return cnt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Code language: Java
class Solution {
    public int deepestLeavesSum(TreeNode root) {
        Deque<TreeNode> st = new ArrayDeque<>();
        if (root != null) st.addLast(root);
        int cnt = 0;
        while (!st.isEmpty()) {
            cnt = 0;
            for (int i = 0, n = st.size(); i < n; ++i) {
                TreeNode cur = st.pollFirst();
                cnt += cur.val;
                if (cur.left != null) st.addLast(cur.left);
                if (cur.right != null) st.addLast(cur.right);
            }
        }
        return cnt;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Code language: C++
class Solution {
public:
    int deepestLeavesSum(TreeNode* root) {
        queue<TreeNode*> st;
        if (root != nullptr) st.push(root);
        int cnt = 0;
        while (!st.empty()) {
            cnt = 0;
            for (int i = 0, n = st.size(); i < n; ++i) {
                TreeNode* cur = st.front(); st.pop();
                cnt += cur->val;
                if (cur->left != nullptr) st.push(cur->left);
                if (cur->right != nullptr) st.push(cur->right);
            }
        }
        return cnt;
    }
};
  • 时间复杂度: \(O(n)\), \(n\) 表示二叉树的结点总数
  • 空间复杂度: \(O(n)\)

DFS

也可以使用记录深度的DFS，递归实现代码写起来比较简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Code language: Python
class Solution:
    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        h, cnt = 0, 0

        def dfs(root: TreeNode, deep: int):
            if root:
                nonlocal h, cnt
                if deep > h:
                    h, cnt = deep, root.val
                elif deep == h:
                    cnt += root.val
                dfs(root.left, deep + 1)
                dfs(root.right, deep + 1)
        
        dfs(root, 1)
        return cnt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Code language: Java
class Solution {
    private int h = 0, cnt = 0;
    public int deepestLeavesSum(TreeNode root) {
        dfs(root, 1);
        return cnt;
    }

    private void dfs(TreeNode root, int deep) {
        if (root == null) return;
        if (deep > h) {
            h = deep; cnt = root.val;
        }
        else if (deep == h) cnt += root.val;
        dfs(root.left, deep + 1);
        dfs(root.right, deep + 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Code language: C++
class Solution {
public:
    int deepestLeavesSum(TreeNode* root) {
        int h = 0, cnt = 0;
        function<void(TreeNode*, int)> dfs = [&](TreeNode* root, int deep) {
            if (root == nullptr) return ;
            if (deep > h) {
                h = deep; cnt = root->val;
            }
            else if (deep == h) cnt += root->val;
            dfs(root->left, deep + 1);
            dfs(root->right, deep + 1);
        };
        dfs(root, 1);
        return cnt;
    }
};
  • 时间复杂度: \(O(n)\), \(n\) 表示二叉树的结点总数
  • 空间复杂度: \(O(n)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往 我的博客 或 Algorithm - Github 查看更多题解

--- ♥ end ♥ ---

欢迎关注我呀~