Breadth-First Search
Level Order Sum
easy
DESCRIPTION
Given the root of a binary tree, return the sum of the nodes at each level. The output should be a list containing the sum of the nodes at each level.
Example 1:
Input:
[1, 3, 4, null, 2, 7, null, 8]
Output: [1, 7, 9, 8]
Example 2:
Input:
[1, 2, 5, 3, null, null, null, null, 4]
Output: [1, 7, 3, 4]
Code Editor
Java
// class TreeNode {
// int val;
// TreeNode left;
// TreeNode right;
// TreeNode() {}
// TreeNode(int val) { this.val = val; }
// TreeNode(int val, TreeNode left, TreeNode right) {
// this.val = val;
// this.left = left;
// this.right = right;Run your code to see results here
Have suggestions or found something wrong?
Explanation
We should recognize that a level-order breadth-first traversal of the binary tree is the most straightforward way to solve this problem.
At each level, we can keep a running sum of the node's values at that level. Then, whenever we finish processing a level (the for-loop for that level finishes), then we can add the sum of the nodes to the output list.
Solution
Java
class Solution {public List<Integer> levelSum(TreeNode root) {if (root == null) {return new ArrayList<>();}List<Integer> nodes = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {// start of a new level hereint levelSize = queue.size();int sum = 0;// process all nodes in the current levelfor (int i = 0; i < levelSize; i++) {TreeNode node = queue.poll();sum += node.val;if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}// we are at the end of the level,// add the sum of the nodes to the output listnodes.add(sum);}return nodes;}}
What is the time complexity of this solution?
1
O(n)
2
O(log m * n)
3
O(1)
4
O(n³)