Sum Root to Leaf Numbers

https://leetcode.com/problems/sum-root-to-leaf-numbers/description/

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Thoughts

和pathSum一个路数，只是这里psum不再只是加上，而是有个特殊处理。

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int res = 0;
    int sumNumbers(TreeNode* root) {
        dfs(root, 0);
        return res;
    }
    
    void dfs(TreeNode *cur, int psum) {
        if (cur == NULL) return;
        psum = psum * 10 + cur->val;
        if (cur->left == NULL && cur->right == NULL) res += psum;
        dfs(cur->left, psum);
        dfs(cur->right, psum);
    }
};

Analysis

时间复杂度为一次遍历O(n)

Ver.2

和pathSum一个路数，都是记录从root往下的psum, 只是这里psum不再只是加上，而是有个特殊处理。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        stack<TreeNode*> s;
        int psum = 0;
        TreeNode *pre = NULL;
        int res = 0;
        const auto push_left = [&](TreeNode *cur) {
            while (cur != NULL) {
                s.push(cur);
                psum = psum * 10 + cur->val;
                cur = cur->left;
            }
            pre = NULL;
        };
        push_left(root);
        while (!s.empty()) {
            const auto cur = s.top();
            if (cur->right != pre) {
                push_left(cur->right);
                continue;
            }
            if (cur->left == NULL && cur->right == NULL) {
                res += psum;
            }
            psum -= cur->val;
            psum /= 10;
            s.pop();
            pre = cur;
        }
        return res;
    }
};