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

    //这道题的本质是让我们记录每一条从根到叶子的路径
    //思路是用栈来做，每抵达一个叶子节点时，就把它从栈中弹出，然后访问栈顶
    //看看栈顶的节点还有没有未访问过的子节点能继续加入的，没有的话就继续弹出。
    //用递归做比较好，不然还得维护每个节点的两个子节点是否有被访问过。
    stack<TreeNode*> s;
    
    void Traverse(TreeNode* root,vector<vector<int> >&results)
    {
        vector<int>CurrentResult;
        if(root==NULL)
            return ;
        //新进栈一个节点。
        s.push(root);
        
        //如果来到了叶子节点，那么就出栈。
        if(root!=NULL && root->left==NULL && root->right==NULL){
            stack<TreeNode*> temp=s;
            //将栈中的内容拷贝到数组中。
            for(int i=0;i<s.size();i++)
            {
                CurrentResult.push_back(temp.top()->val);
                temp.pop();
            }
            s.pop();
            results.push_back(CurrentResult);
            //CurrentResult.clear();
            return;
        }
        
        //先尝试将其左右子节点也加入栈中。
        Traverse(root->left,results);
        Traverse(root->right,results);
        //倘若左右子树的递归已经都完成了，说明现在该回退了。
        s.pop();

        return;
    }
    
    int sumNumbers(TreeNode* root) {
        // write code here
        vector<vector<int> >results;
        Traverse(root,results);
        //所有路径和
        int sum=0;
        //位数
        int place=1;
        //单条路径和
        int localSum=0;
        for(auto result:results)
        {
            place=1;
            localSum=0;
            for(auto number:result)
            {
                localSum+=number*place;
                place*=10;
            }
            sum+=localSum;
        }
        return sum;
    }