Formatted question description: https://leetcode.ca/all/1302.html

1302. Deepest Leaves Sum (Medium)

Given a binary tree, return the sum of values of its deepest leaves.

Example 1:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

Constraints:

The number of nodes in the tree is between 1 and 10^4.
The value of nodes is between 1 and 100.

Related Topics:
Tree, Depth-first Search

Solution 1. DFS

// OJ: https://leetcode.com/problems/deepest-leaves-sum/
// Time: O(N)
// Space: O(H)
class Solution {
    int getDepth(TreeNode *root) {
        return root ? 1 + max(getDepth(root->left), getDepth(root->right)) : 0;
    }
    int getSumAtDepth(TreeNode *root, int d, int depth) {
        if (!root) return 0;
        if (d == depth) return root->val;
        return getSumAtDepth(root->left, d + 1, depth) + getSumAtDepth(root->right, d + 1, depth);
    }
public:
    int deepestLeavesSum(TreeNode* root) {
        int depth = getDepth(root);
        return getSumAtDepth(root, 1, depth);
    }
};

Solution 2. BFS

// OJ: https://leetcode.com/problems/deepest-leaves-sum/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int deepestLeavesSum(TreeNode* root) {
        if (!root) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int ans;
        q.push(root);
        while (q.size()) {
            int cnt = q.size();
            ans = 0;
            while (cnt--) {
                auto node = q.front();
                q.pop();
                ans += node->val;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return ans;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int deepestLeavesSum(TreeNode root) {
        if (root == null)
            return 0;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int deepestSum = 0;
        while (!queue.isEmpty()) {
            int curSum = 0;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                curSum += node.val;
                TreeNode left = node.left, right = node.right;
                if (left != null)
                    queue.offer(left);
                if (right != null)
                    queue.offer(right);
            }
            deepestSum = curSum;
        }
        return deepestSum;
    }
}

############

/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    public int deepestLeavesSum(TreeNode root) {
        Deque<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        int ans = 0;
        while (!q.isEmpty()) {
            ans = 0;
            for (int n = q.size(); n > 0; --n) {
                root = q.pollFirst();
                ans += root.val;
                if (root.left != null) {
                    q.offer(root.left);
                }
                if (root.right != null) {
                    q.offer(root.right);
                }
            }
        }
        return ans;
    }
}

// OJ: https://leetcode.com/problems/deepest-leaves-sum/
// Time: O(N)
// Space: O(H)
class Solution {
    int getDepth(TreeNode *root) {
        return root ? 1 + max(getDepth(root->left), getDepth(root->right)) : 0;
    }
    int getSumAtDepth(TreeNode *root, int d, int depth) {
        if (!root) return 0;
        if (d == depth) return root->val;
        return getSumAtDepth(root->left, d + 1, depth) + getSumAtDepth(root->right, d + 1, depth);
    }
public:
    int deepestLeavesSum(TreeNode* root) {
        int depth = getDepth(root);
        return getSumAtDepth(root, 1, depth);
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        q = deque([root])
        while q:
            ans = 0
            for _ in range(len(q)):
                root = q.popleft()
                ans += root.val
                if root.left:
                    q.append(root.left)
                if root.right:
                    q.append(root.right)
        return ans

############

# 1302. Deepest Leaves Sum
# https://leetcode.com/problems/deepest-leaves-sum/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        deq = collections.deque([root])
        res = 0
        
        while deq:
            l = len(deq)
            res = 0
            
            while l:
                node = deq.popleft()
                res += node.val
                
                for n in (node.left, node.right):
                    if n: deq.append(n)
                l -= 1
            

        return res

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func deepestLeavesSum(root *TreeNode) int {
	q := []*TreeNode{root}
	ans := 0
	for len(q) > 0 {
		ans = 0
		for n := len(q); n > 0; n-- {
			root = q[0]
			q = q[1:]
			ans += root.Val
			if root.Left != nil {
				q = append(q, root.Left)
			}
			if root.Right != nil {
				q = append(q, root.Right)
			}
		}
	}
	return ans
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function deepestLeavesSum(root: TreeNode | null): number {
    const queue = [root];
    let res = 0;
    while (queue.length !== 0) {
        const n = queue.length;
        let sum = 0;
        for (let i = 0; i < n; i++) {
            const { val, left, right } = queue.shift();
            sum += val;
            left && queue.push(left);
            right && queue.push(right);
        }
        res = sum;
    }
    return res;
}

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, depth: i32, max_depth: &mut i32, res: &mut i32) {
        if let Some(node) = root {
            let node = node.borrow();
            if node.left.is_none() && node.right.is_none() {
                if depth == *max_depth {
                    *res += node.val;
                } else if depth > *max_depth {
                    *max_depth = depth;
                    *res = node.val
                }
                return;
            }
            Self::dfs(&node.left, depth + 1, max_depth, res);
            Self::dfs(&node.right, depth + 1, max_depth, res);
        }
    }

    pub fn deepest_leaves_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut res = 0;
        let mut max_depth = 0;
        Self::dfs(&root, 0, &mut max_depth, &mut res);
        res
    }
}

1302 - Deepest Leaves Sum

1302. Deepest Leaves Sum (Medium)

Solution 1. DFS

Solution 2. BFS

All Problems

All Solutions

Welcome to Subscribe On Youtube

1302. Deepest Leaves Sum (Medium)

Solution 1. DFS

Solution 2. BFS

All Problems

All Solutions