129. Sum Root to Leaf Numbers - cocoder39/coco39_LC GitHub Wiki

129. Sum Root to Leaf Numbers

bfs

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        res = 0
        if root:
            queue = [(root, 0)]
        while queue:
            node, num = queue.pop()
            if not node.left and not node.right:
                res += 10 * num + node.val
            else:
                if node.left:
                    queue.append((node.left, 10 * num + node.val))
                if node.right:
                    queue.append((node.right, 10 * num + node.val))
        return res

preorder traversal

compare it with another dfs approach which gets value of each path. This solution is smart as it checks contribution of each node but doesn't require the explicit value of each path

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(node, num):
            if not node.left and not node.right:
                return num * 10 + node.val
            
            res = 0
            num = num * 10 + node.val
            if node.left:
                res += dfs(node.left, num)
            if node.right:
                res += dfs(node.right, num)
            return res

        return dfs(root, 0)

another dfs approach to get value of each path, which requires extra space to carry contribution of each path

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        res = self.helper(root, 0)
        return sum(res)
    
    def helper(self, node, path) -> list:
        if not node.left and not node.right:
            return [10*path + node.val]
        
        left, right = [], []
        if node.left:
            left = self.helper(node.left, 10*path + node.val)
        if node.right:
            right = self.helper(node.right, 10*path + node.val)
        return left + right
        
        

dfs, O(n) time and O(height) space for call stack

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        if(! root) {
            return 0;
        }
        int sum = 0;
        helper(sum, 0, root);
        return sum;
    }
private:
    void helper(int &sum, int path, TreeNode* root){
        path += root->val;
        if (! root->left && ! root->right) {
            sum += path;
        }
        if (root->left) {
            helper(sum, path*10, root->left);
        }
        if (root->right) {
            helper(sum, path*10, root->right);
        }
    }
};