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

复习：二叉树的dfs（用递归或者用栈）和bfs，这里好像和先序遍历有点区别

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
#include <stack>
#include <math.h>
#include <queue>
stack<TreeNode*> s;
stack<int> s_layer;
queue<TreeNode*> q;
class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
//     void traverse(TreeNode* node, int& cur, int& res){
//         cur = cur * 10 + node->val;
//         if(node->left == NULL and node->right == NULL){
//             res += cur;
//         }
//         if(node->left != NULL){
//             traverse(node->left, cur, res);
//         }
//         if(node->right != NULL){
//             traverse(node->right, cur, res);
//         }
//         cur = cur / 10;
//     }
//     void traverse(TreeNode* node, int& cur, int& res){
//         s.push(node);
//         s_layer.push(0);
//         int layer = 0;
//         while(s.size() > 0){
//             TreeNode* n = s.top();
//             s.pop();
//             int l = s_layer.top();
//             s_layer.pop();
//             cur = cur / (pow(10, layer - l + 1));
//             layer = l;
//             cur = cur * 10 + n->val;
//             while(n->left != NULL or n->right != NULL){
                
//                 layer += 1;
//                 if(n->left != NULL){
//                     cur = cur * 10 + n->left->val;
                    
//                     if(n->right != NULL){
//                         s.push(n->right);
//                         s_layer.push(layer);
//                     }
//                     n = n->left;
//                 }else{
//                     cur = cur * 10 + n->right->val;
//                     n = n->right;
//                 }
                
//             }
//             res += cur;
            
//         }
//     }
    void traverse(TreeNode *node, int &cur, int &res){
        q.push(node);
        while(!q.empty()){
            TreeNode* n = q.front();
            q.pop();
            if(n->left == NULL and n->right == NULL){
                res += n->val;
            }else{
                if(n->left != NULL){
                    TreeNode *l = n->left;
                    l->val = n->val * 10 + l->val;
                    q.push(l);
                }
                if(n->right != NULL){
                    TreeNode *r = n->right;
                    r->val = n->val * 10 + r->val;
                    q.push(r);
                }
            }
        }
    }
    int sumNumbers(TreeNode* root) {
        // write code here
        int res = 0;
        int cur = 0;
        
        if(root == NULL){
            return 0;
        }
        traverse(root, cur, res);
        return res;
    }
};