leetcode--1302--层数最深叶子节点的和

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

示例：

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

提示：

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

链接：https://leetcode-cn.com/problems/deepest-leaves-sum

思路：
1、BFS层次遍历

Python代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):

    def __init__(self):
        self.ret = []

    def deepestLeavesSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0

        deque = [root]

        while deque:
            tmp = []
            nex = []
            for item in deque:
                tmp.append(item.val)
                if item.left:
                    nex.append(item.left)
                if item.right:
                    nex.append(item.right)
            deque = nex
            self.ret.append(tmp)
        return sum(self.ret[-1])

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:

    vector<vector<int> > ret;

    int deepestLeavesSum(TreeNode* root) {

        if (root == nullptr){
            return 0;
        }
        vector<TreeNode*> deque;
        deque.push_back(root);

        while (deque.size()>0){
            vector<TreeNode*> nex;
            vector<int> tmp;
            for(auto item : deque){
                tmp.push_back(item->val);
                if(item->left != nullptr){
                    nex.push_back(item->left);
                }
                if (item->right != nullptr){
                    nex.push_back(item->right);
                }
            }
            deque.swap(nex);
            ret.push_back(tmp);
        }
        auto result = ret[ret.size()-1];
        int ans=0;
        for (auto i : result){
            ans += i;
        }
        return ans;
    }
};