1302. Deepest Leaves Sum

⚡문제정보

 

https://leetcode.com/problems/deepest-leaves-sum/

Deepest Leaves Sum - LeetCode

가장 깊은 잎의 값들을 반환하면 되는 문제입니다.

위 이진트리에서 가장 깊은 depth에 있는 값은 7과 8이기 때문에

7 + 8 = 15로 15를 반환하면 되는 문제입니다.

 * 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)
 * }

이진트리는 다음과 같은 형태로 주어집니다.

left값이 있으면 this.left에 값이 할당되고 없다면 null이 할당되는 식이네요

---

🔍접근방법

1. 먼저 DFS 탐색을 통해 depth를 구한다.
2. 얻은 depth를 기반으로 맨끝값을 구한다

---

😑나의 풀이

var deepestLeavesSum = function(root) {
    const depthCheck = (root) => {
        if(root === null) return 0
        return Math.max(depthCheck(root.left) +1 , depthCheck(root.right)+1  )
    }
    
    const realDepth = depthCheck(root)
    
    const calculate = (root,depth) => {
        if(root === null) return 0
        if(depth === realDepth) return root.val
        return calculate(root.left, depth+1) + calculate(root.right , depth+1) 
    }
    
    const result = calculate(root,1)
    return result
    
};

외국인의 풀이를 참고해서 제가 해석하기 좋은 쪽으로 코드를 바꿔봤습니다.

그런데 이렇게 탐색을하면 DFS 탐색을 두번이나 하는 문제점이 있습니다.

똑같은 탐색을 두번이나하는건 좀 비효율적이어보이는데 해결할 방법이 없을까요?

제 생각엔 모든 깊이의 값의 합을 어딘가에 저장해두면 될 것 같습니다.

 

var deepestLeavesSum = function(root) {
    let cache = [];
    const rec = (root, depth = 0) => {
        if (!root) return 0;
        cache[depth] = (cache[depth] || 0) + root.val;
        rec(root.left, depth + 1);
        rec(root.right, depth + 1);
    }
    rec(root);
    return cache[cache.length - 1];
};

제생각이랑 같은 풀이네요

만약 이렇게 코드를 작성한다면 각 깊이의 합이 모두 저장될테고

맨끝 배열의 값이 곧 가장 깊은 depth의 값이 됩니다.