[Leetcode] 129. Sum Root to Leaf Numbers - JS

https://leetcode.com/problems/sum-root-to-leaf-numbers/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
0-9까지 숫자를 포함하는 이진트리가 주어진다.
각 루트에서 리프노드까지 경로는 숫자를 의미한다. 1 -> 2 -> 3은 123이다.
모든 루트에서 리프노드까지의 숫자의 합을 반환하라.
테스트케이스의 답은 32bit 정수이다.

제한조건
--------------------
- 노드의 갯수는 1 ~ 1000개이다.
- 0 <= Node.val <= 9
- tree의 깊이는 10을 초과하지 않는다.

 

2. 접근 방법

접근방법
--------------------
재귀함수로 순회할 때, node와 누적합을 전달한다.
자식 노드가 없을 때, 현재까지의 누적합을 반환한다.

left 자식노드와 right 자식노드의 누적합을 더한 값을 반환한다.

 

 

3. 코드

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var sumNumbers = function(root) {

    function rootToLeaf(node, currentSum) {
        if (!node) {
            return 0
        }
        currentSum = currentSum * 10 + node.val;

        if (!node.left && !node.right) {
            return currentSum
        }
        
        return rootToLeaf(node.left, currentSum) + rootToLeaf(node.right, currentSum)
    }

    return rootToLeaf(root,0)
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n) 

- 공간복잡도: O(1)

 

[Leetcode] 112. Path Sum - JS 이 문제와 비슷하게 루트노드에서 리프노드까지 도달할 때, 합계값을 반환하고

left 자식과 right 자식과 누적합을 재귀함수로 호출해준다.