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

数据结构：栈用于存储树的节点，count是一条路径的值，sum是所有路径的值。

首先创建一个栈用来存储当前路径，从根节点开始遍历树，遍历到叶子节点时便是一条完整的路径。此时该栈所有节点的数值之和也就是这条路径的长度，将该长度与之前的长度sum相加得到当前所有路径的长度之和。然后将该叶子节点提出栈，栈顶指针指向其父节点，开始寻找父节点有没有其他孩子，继而循环遍历父节点的其他孩子节点，直到找到下一条路径。以此循环，直到找到所有路径为止。

#include <stack>
class Solution {
  public:
    /**
     * @param root TreeNode类
     * @return int整型
     */
    int sumNumbers(TreeNode* root) {
        // write code here
        if(root == nullptr)
            return 0;
        stack<TreeNode*> qStack;
        qStack.push(root);
        int sum = 0;
        int count = 0;
        count += root->val;
        dsp(qStack,sum,count);
        return sum;
    }

    void dsp(stack<TreeNode*> &qStack, int &sum,int &count) {
        if (qStack.top()->left == nullptr && qStack.top()->right == nullptr) {
            sum += count;
            count = (count - qStack.top()->val)/10;
            qStack.pop();
            return;
        }
        if (qStack.top()->left != nullptr) {
            qStack.push(qStack.top()->left);
            count =count*10 + qStack.top()->val;
            dsp(qStack,sum,count);
        }
        if (qStack.top()->right != nullptr) {
            qStack.push(qStack.top()->right);
            count =count*10 + qStack.top()->val;
            dsp(qStack,sum,count);
        }
        count = (count - qStack.top()->val)/10;
        qStack.pop();
        return;
    }
};