题解 | #二叉树根节点到叶子节点的所有路径和#

/*
1.方案1 递归
采用路径和看成每个支路之和；
1）如果达到根节点将当前支路的和返回；
2）如果没有则需要将左右节点的和相加

2.方案2 dfs;
双向队列对每层数据进行存与读
保存层每个节点当前的数值；
如果当前节点的左右节点为空则直接加入；
没有则继续

/
/*

• struct TreeNode {
• int val;
• struct TreeNode *left;
• struct TreeNode *right;
• };
• /

class Solution {
public:
/*
*
* @param root TreeNode类
* @return int整型
/
//递归
// int tr(TreeNoderoot,int sum)
// {
// if(!root) return 0;
// sum=sum*10+root->val;
// if(!root->left&&!root->right) return sum;
// return tr(root->left,sum)+tr(root->right,sum);
// }
// int sumNumbers(TreeNode root) {
// // write code here
// return tr(root,0);

//dfs
int sumNumbers(TreeNode* root) {
    int Ans=0;
    //存储每条支路上的数值
    vector<int> ans;
    deque<TreeNode*>dq;
    if(root) {dq.push_back(root);ans.push_back(root->val);}
    while(!dq.empty())
    {
        vector<int>temp;
        int l=dq.size();
        for(int i=0;i<l;i++)
        {
            TreeNode* R=dq.front();
            dq.pop_front();
            if(R->left){
                dq.push_back(R->left);
                temp.push_back(ans[i]*10+R->left->val);//ans=temp;
            }
            if(R->right)
            {
                dq.push_back(R->right);
                temp.push_back(ans[i]*10+R->right->val);
                //ans=temp;
            }
            //当不存在左右节点是表明已经到达根节点直接叠加即可
            if(!R->left&&!R->right) Ans+=ans[i];

        }

// //如果使用当前层的数值更新之前的ans
if(!dq.empty())
ans=temp;
}

    return Ans;
 }

};