129. Sum Root to Leaf Numbers

LeetCode Link (opens in a new tab)

Tree DFS

Description

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

• For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123. Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

Example cases

Example 1:

• Input: root = [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: root = [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.

Constraints

• The number of nodes in the tree is in the range [1, 1000].
• 0 <= Node.val <= 9
• The depth of the tree will not exceed 10.

Approach

root 노드부터 모든 leaf 노드까지의 경로에 있는 숫자를 이어붙인 숫자들의 합을 구하는 문제이다.
dfs 문제에서 쉽게 볼 수 있는 탐색한 경로에 대한 문제이다. dfs로 탐색할 때, 두번째 인자로 path 값을 두고 탐색할 때마다 path에 해당 값을 string으로 붙인다.
string으로 변환해서 저장하는 이유는 2번 예시에서 4->9->5 순서로 탐색했을 때, 4 + 9 + 5가 아니라 '4' + '9' + '5'로 해야 495를 구할 수 있기 때문이다.
이점만 유의하면 쉽게 풀 수 있고, leaf에 다다랐을 때, (left right가 모두 null) 지금까지의 경로를 합에 더한다.

Solution Code

var sumNumbers = function(root) {
  let ans = 0
  const dfs = (node, path = '') => {
    if (!node) {
      return
    }
    if (!node.left && !node.right) {
      ans += Number(path + `${node.val}`)
      return
    }
 
    dfs(node.left, path + `${node.val}`)
    dfs(node.right, path + `${node.val}`)
  }
 
  dfs(root)
  return ans
};

Complexity

• time complexity : $O(n)$
• space complexity : $O(1)$