솔루션: 가장 깊은 잎 합계

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 들었거나 유용하다고 생각되면 이 게시물에 좋아요를 누르거나 찬성 투표my solution post on Leetcode's forums를 해주세요.

Leetcode 문제 #1302(중간): 가장 깊은 리프 합계

설명:

(다음으로 이동: Solution Idea || 코드: JavaScript | Python | Java | C++ )

Given the root of a binary tree, return the sum of values of its deepest leaves.

예:

Example 1:
Input:	root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output:	15
Visual:

Example 2:
Input:	root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output:	19

제약:

• The number of nodes in the tree is in the range [1, 104].
• 1 <= Node.val <= 100

아이디어:

(다음으로 이동: Problem Description || 코드: JavaScript | Python | Java | C++ )

이진 트리의 특정 행에 대한 정보를 찾으라는 요청을 받았을 때 일반적인 생각은 BFS(폭 우선 검색) 방식을 사용하는 것입니다. BFS 접근 방식은 일반적으로 대기열 데이터 구조(q)를 사용하여 적절한 순서로 트리의 노드를 처리합니다.

요령은 행을 시작할 때 대기열(qlen)의 길이를 기록하여 한 번에 하나의 행을 처리하는 것입니다. 그렇게 많은 노드를 처리하면 현재 행이 끝났고 q의 나머지 항목은 다음 행에서 가져온 것임을 알 수 있습니다. 이는 중첩 루프를 사용하여 쉽게 수행할 수 있습니다.

이 경우 노드를 처리한다는 것은 단순히 행에 대한 누계(ans)를 누적한 다음 노드의 모든 자식을 대기열 끝으로 이동하는 것을 의미합니다.

새 행을 시작할 때 ans를 다시 0으로 재설정한 다음 q가 비어 있을 때까지 행을 계속 처리할 수 있습니다. ans의 마지막 값이 최종 답이 되어야 하므로 ans를 반환해야 합니다.

또는 재귀와 함께 DFS(깊이 우선 검색) 접근 방식을 사용하여 이진 트리를 탐색할 수 있습니다. 행 깊이(lvl)를 재귀 함수(dfs)의 인수로 전달하면 lvl을 인덱스(sums[lvl])로 사용하여 행 합계(sums) 배열의 값을 업데이트하는 데 사용할 수 있습니다. 그런 다음 단순히 합계의 마지막 값을 답으로 반환할 수 있습니다.

구현:

네 가지 언어 간에는 약간의 차이만 있습니다.

자바스크립트 코드:

(다음으로 이동: Problem Description || Solution Idea )


BFS 포함:

var deepestLeavesSum = function(root) {
    let q = [root], ans, qlen, curr
    while (q.length) {
        qlen = q.length, ans = 0
        for (let i = 0; i < qlen; i++) {
            curr = q.shift(), ans += curr.val
            if (curr.left) q.push(curr.left)
            if (curr.right) q.push(curr.right)
        }
    }
    return ans
};

재귀 DFS 포함:

var deepestLeavesSum = function(root) {
    let sums = []
    const dfs = (node, lvl) => {
        if (lvl === sums.length) sums[lvl] = node.val
        else sums[lvl] += node.val
        if (node.left) dfs(node.left, lvl+1)
        if (node.right) dfs(node.right, lvl+1)
    }
    dfs(root, 0)
    return sums[sums.length-1]
};

파이썬 코드:

(다음으로 이동: Problem Description || Solution Idea )


BFS 포함:

class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        q, ans, qlen, curr = [root], 0, 0, 0
        while len(q):
            qlen, ans = len(q), 0
            for _ in range(qlen):
                curr = q.pop(0)
                ans += curr.val
                if curr.left: q.append(curr.left)
                if curr.right: q.append(curr.right)
        return ans

재귀 DFS 포함:

class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        sums = []
        def dfs(node: TreeNode, lvl: int):
            if lvl == len(sums): sums.append(node.val)
            else: sums[lvl] += node.val
            if node.left: dfs(node.left, lvl+1)
            if node.right: dfs(node.right, lvl+1)
        dfs(root, 0)
        return sums[-1]

자바 코드:

(다음으로 이동: Problem Description || Solution Idea )


BFS 포함:

class Solution {
    public int deepestLeavesSum(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int ans = 0, qlen = 0;
        while (q.size() > 0) {
            qlen = q.size();
            ans = 0;
            for (int i = 0; i < qlen; i++) {
                TreeNode curr = q.poll();
                ans += curr.val;
                if (curr.left != null) q.add(curr.left);
                if (curr.right != null) q.add(curr.right);
            }
        }
        return ans;
    }
}

재귀 DFS 포함:

class Solution {
    List<Integer> sums = new ArrayList<>();
    public int deepestLeavesSum(TreeNode root) {
        dfs(root, 0);
        return sums.get(sums.size()-1);
    }
    public void dfs(TreeNode node, int lvl) {
        if (lvl == sums.size()) sums.add(node.val);
        else sums.set(lvl, sums.get(lvl) + node.val);
        if (node.left != null) dfs(node.left, lvl+1);
        if (node.right != null) dfs(node.right, lvl+1);
    }
}

C++ 코드:

(다음으로 이동: Problem Description || Solution Idea )


BFS 포함:

class Solution {
public:
    int deepestLeavesSum(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int ans = 0, qlen = 0;
        while (q.size() > 0) {
            qlen = q.size(), ans = 0;
            for (int i = 0; i < qlen; i++) {
                TreeNode* curr = q.front(); q.pop();
                ans += curr->val;
                if (curr->left) q.push(curr->left);
                if (curr->right) q.push(curr->right);
            }
        }
        return ans;
    }
};

재귀 DFS 포함:

class Solution {
public:
    vector<int> sums;
    int deepestLeavesSum(TreeNode* root) {
        dfs(root, 0);
        return sums.back();
    }
    void dfs(TreeNode* node, int lvl) {
        if (lvl == sums.size()) sums.push_back(node->val);
        else sums[lvl] += node->val;
        if (node->left) dfs(node->left, lvl+1);
        if (node->right) dfs(node->right, lvl+1);
    }
};