[LeetCode] 129. Sum Root to Leaf Numbers

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

Use DFS approach to travel from root to every leafs.

A rescurisve approach:

Time Complexity = O ( N )

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    int dfs(TreeNode node, int tmp) {
        tmp = tmp  * 10 + node.val;
        if (node.left == null && node.right == null) {
            return tmp;
        }

        int result = 0; 
        result += (node.left != null) ? dfs(node.left, tmp) : 0;
        result += (node.right != null) ? dfs(node.right, tmp) : 0;
        return result;
    }
}

An iterative approach:

Time Complexity = O ( N )

# 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: TreeNode) -> int:
        result = 0
        stack = [(0, root)]
        
        while stack:
            num, node = stack.pop()
            num =  num * 10 + node.val
            
            if not node.left and not node.right:
                result += num
            else:
                if node.right:
                    stack.append((num, node.right))
                if node.left:
                    stack.append((num, node.left))
        
        return result

Edited on 03/13/2023. Replace the recursive solution with a Java based solution.

Edited on 04/24/2021. Refactor the recursive solution.

Edited on 04/24/2021. Add the iterative solution.