129-根到叶子节点的和

LeetCode 129. Sum Root to Leaf Numbers

LeetCode-129

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.
Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

Example 1:

Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

method: 回溯

每条根到叶子节点的路径都可以组成一个数字，求这些数字的和

简单的回溯，因为要检查是不是根节点，所以先确保不是空节点

int res;
void traversal(TreeNode *root, int num) {
    if (!root->left && !root->right) {
        res += num * 10 + root->val;    // 加上根节点的值
        return;
    }
    if (root->left) traversal(root->left, num * 10 + root->val);
    if (root->right) traversal(root->right, num * 10 + root->val);
}
int sumNumbers(TreeNode* root) {
    traversal(root, 0);
    return res;
}

也可以这样写

int res = 0;
void dfs(TreeNode *root, int sum) {
    if (!root) return;
    sum = sum * 10 + root->val;
    if (!root->left && !root->right) {
        res += sum;
    }
    dfs(root->left, sum);
    dfs(root->right, sum);
    // sum /= 10;  不需要在去掉，因为是按值传递的
}
int sumNumbers(TreeNode* root) {
    dfs(root, 0);
    return res;
}