Skip to content

Latest commit

 

History

History

129

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 

README.md

129. Sum Root to Leaf Numbers (Medium)

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.

Note: A leaf is a node with no children.

Example:

Input: [1,2,3]
    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.

Example 2:

Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Related Topics:
Tree, Depth-first Search

Similar Questions:

Solution 1. Pre-order traversal (Recursive)

// OJ: https://leetcode.com/problems/sum-root-to-leaf-numbers/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
    int ans = 0;
    void dfs(TreeNode *root, int sum) {
        if (!root) return;
        sum = sum * 10 + root->val;
        if (!root->left && !root->right) ans += sum;
        dfs(root->left, sum);
        dfs(root->right, sum);
    }
public:
    int sumNumbers(TreeNode* root) {
        dfs(root, 0);
        return ans;
    }
};

Or

// OJ: https://leetcode.com/problems/sum-root-to-leaf-numbers/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
public:
    int sumNumbers(TreeNode* root, int sum = 0) {
        if (!root) return 0;
        sum = 10 * sum + root->val;
        if (!root->left && !root->right) return sum;
        return sumNumbers(root->left, sum) + sumNumbers(root->right, sum);
    }
};

Solution 2. Pre-order traversal (Iterative)

// OJ: https://leetcode.com/problems/sum-root-to-leaf-numbers/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        if (!root) return 0;
        stack<pair<TreeNode*, int>> s;
        s.emplace(root, 0);
        int ans = 0;
        while (s.size()) {
            auto p = s.top();
            root = p.first;
            int sum = p.second * 10 + root->val;
            s.pop();
            if (!root->left && !root->right) ans += sum;
            if (root->right) s.emplace(root->right, sum);
            if (root->left) s.emplace(root->left, sum);
        }
        return ans;
    }
};