Skip to content

129. Sum Root to Leaf Numbers

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

js
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function(root) {
    const paths = []
    traversePaths(root, [], paths)
    return paths.reduce((ret, path) => {
        const num = path.reduce((sum, node) => {
            sum = sum * 10 + node.val
            return sum
        }, 0)
        return ret + num
    }, 0)
};

function traversePaths(root, path, paths) {
    if (!root) {
        return
    }
    if (!root.left && !root.right) {
        paths.push([...path, root])
    }
    if (root.left) {
        traversePaths(root.left, [...path, root], paths)
    }
    if (root.right) {
        traversePaths(root.right, [...path, root], paths)
    }
}
py
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution(object):

    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        paths = []
        self.traversePaths(root, [], paths)
        sumVal = 0
        for path in paths:
            pathSum = 0
            for node in path:
                pathSum = pathSum * 10 + node.val
            sumVal += pathSum
        return sumVal

    def traversePaths(self, root, path, paths):
        if not root:
            return
        if not root.left and not root.right:
            paths.append([*path, root])
        if root.left:
            self.traversePaths(root.left, [*path, root], paths)
        if root.right:
            self.traversePaths(root.right, [*path, root], paths)
go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumNumbers(root *TreeNode) int {
	paths := &[][]*TreeNode{}
	traversePaths(root, []*TreeNode{}, paths)
	sum := 0
	for _, path := range *paths {
		pathSum := 0
		for _, node := range path {
			pathSum = pathSum*10 + node.Val
		}
		sum += pathSum
	}
	return sum
}

func traversePaths(root *TreeNode, path []*TreeNode, paths *[][]*TreeNode) {
	if root == nil {
		return
	}
	newPath := append([]*TreeNode{}, path...)
	newPath = append(newPath, root)
	if root.Left == nil && root.Right == nil {
		*paths = append(*paths, append([]*TreeNode{}, newPath...))
	}
	if root.Left != nil {
		traversePaths(root.Left, append([]*TreeNode{}, newPath...), paths)
	}
	if root.Right != nil {
		traversePaths(root.Right, append([]*TreeNode{}, newPath...), paths)
	}
}