SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

Given the root of a binary tree, each root-to-leaf path represents a number formed by the concatenation of the node values along the path. The task is to find the total sum of these numbers for all root-to-leaf paths in the binary tree.

Intuition

The problem can be approached using a depth-first search (DFS) strategy. As we traverse each path from the root to the leaves, we construct the number represented by that path. When we reach a leaf node, we add the constructed number to a running total. This can be done recursively by keeping track of the current number as we move down the tree.

Approach

1. Define a helper function dfs that takes a node and the current number constructed so far.
2. If the node is None, return 0 because there is no number to add.
3. Update the current number by appending the node's value to the number.
4. If the node is a leaf (i.e., it has no left or right children), return the current number as it represents a complete root-to-leaf path.
5. Recursively call dfs on the left and right children, summing the results to get the total sum for the subtree rooted at the current node.
6. Start the DFS from the root node with an initial number of 0.

Complexity

Time Complexity:

O(N), where N is the number of nodes in the tree. Each node is visited once.

Space Complexity:

O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case (skewed tree), H could be N. In the best case (balanced tree), H is log(N).

Code

C++

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
private:
    int dfs(TreeNode* node, int num) {
        if (!node) {
            return 0;
        }
        num = num * 10 + node->val;

        if (!node->left && !node->right) {
            return num;
        }
        return dfs(node->left, num) + dfs(node->right, num);
    }
};

Python

# 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:
        def dfs(node, num):
            if not node:
                return 0
            num = num * 10 + node.val
            if not node.left and not node.right:
                return num
            return dfs(node.left, num) + dfs(node.right, num)
        
        return dfs(root, 0)

Java

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    private int dfs(TreeNode node, int num) {
        if (node == null) {
            return 0;
        }
        num = num * 10 + node.val;

        if (node.left == null && node.right == null) {
            return num;
        }
        return dfs(node.left, num) + dfs(node.right, num);
    }
}

JavaScript

var sumNumbers = function (root) 
{
    const dfs = (node, num) => {
        if (!node) {
            return 0;
        }
        num = num * 10 + node.val;

        if (!node.left && !node.right) {
            return num;
        }
        return dfs(node.left, num) + dfs(node.right, num);
    }
    return dfs(root, 0);
};