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

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int sumNumbers(TreeNode* root) {
        // write code here
        //非递归方式的深度优先遍历
        //深度优先遍历本质上和前序遍历没有什么区别，所以就是前序遍历的非递归方式
        if(root==NULL)
            return 0;
        int res=0;//最终的返回结果
        stack<TreeNode*> nodeStack;//这个栈专门用来存储节点
        stack<int> dataStack;//这个栈用来存储值
        nodeStack.push(root);//把根节点放入栈中
        dataStack.push(root->val);//把根节点的值放入栈中，默认根节点的父节点的权值为0
        while(!nodeStack.empty()&&!dataStack.empty()){//当栈不为空时
            TreeNode*node=nodeStack.top();
            nodeStack.pop();
            int value=dataStack.top();
            dataStack.pop();
            //先放右孩子再放左孩子
            if(node->right!=NULL){
                nodeStack.push(node->right);
                dataStack.push(value*10+node->right->val);
            }
            if(node->left!=NULL){//左孩子不为空
                nodeStack.push(node->left);
                dataStack.push(value*10+node->left->val);
            }
            if(node->left==NULL&&node->right==NULL){//说明已经到了叶子节点
                res+=value;
            }
        }
        return res;
    }
};