1302. Deepest Leaves Sum.md

1302. Deepest Leaves Sum

---

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.

---

Solution

• java

  • mine

    DFS Runtime: 2 ms, faster than 55.86%,Memory Usage: 40.9 MB, less than 100.00% of Java online submissions

    // O(N)time O(N)space
    public int deepestLeavesSum(TreeNode root) {
        List<List<Integer>> record = new ArrayList<>();
        dfs(root, 0, record);
        
        List<Integer> list = record.get(record.size() - 1);
        int res = 0;
        for(Integer i : list){
            res+=i;
        }
        return  res;
    }
    
    public void dfs(TreeNode node, int level, List<List<Integer>> record){
        if(node == null){
            return;
        }
        int size = record.size();
        List<Integer> temp;
        if(size <= level){
            temp = new ArrayList<>();
            record.add(temp);
        }else{
            temp = record.get(level);
        }
        temp.add(node.val);
        record.set(level, temp);
        dfs(node.left, level + 1, record);
        dfs(node.right, level + 1, record);
    }
    

  • the most votes Runtime: 3 ms, faster than 50.31%, Memory Usage: 40.3 MB, less than 100.00% of Java online submissions

    // O(N)time O(N)space
    public int deepestLeavesSum(TreeNode root) {
        int res = 0, i;
        LinkedList<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        while (!q.isEmpty()) {
            for (i = q.size() - 1, res = 0; i >= 0; --i) {
                TreeNode node = q.poll();
                res += node.val;
                if (node.right != null) q.add(node.right);
                if (node.left  != null) q.add(node.left);
            }
        }
        return res;
    }