[Leetcode] 1302. Deepest Leaves Sum

문제 요약

• 알고리즘 분류: DFS, 백트래킹, Tree, Hash
• 난이도: Medium
• 문제내용:
  
  • 이진 트리에서 가장 깊은 노드 합을 구하여라
• 사이트 주소: https://leetcode.com/problems/deepest-leaves-sum/description/

문제풀이 

 이번 문제는 아래 트리 자료구조 통해서 가장 깊은 노드의 합을 구하는 것이다. 트리, 깊이 우선 탐색, 백트레킹에 관한 개념은 아래 글에서 확인 해보면된다.

• 트리: https://jih3508.tistory.com/87
• 백트레킹: https://jih3508.tistory.com/84
• 깊이 우선 탐색(DFS): https://jih3508.tistory.com/94

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Java

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
}

 

위 트리예제를 보면 level3 부분을 찾아서 더하면 된다. 구현은 아래와 같이 하면된다.

1. 각 레벨마다 key-value로 저장하는 자료구조 선언한다. key는 레벨 value는 노드 값을 담는 리스트로 선언한다.
2. dfs함수를 만든다. 파라미터는 TreeNode와 level을 선언한다. dfs초기에 rootNode와 0으로 시작한다.
3. dfs함수에서는 key-value 자로구조에서   level에 현재 노드값을 리스트추가한다.
4. 왼쪽 노드, 오른쪽 노드있을경우 그 다음 노드에 현재 level +1로 넘긴다.
5. dfs탐색 끝내면 level을 최대 값을 구하고 최대 level 리스트 합을 리턴한다.

DFS탐색 부분은 아래같이 구현 하면된다.

Python

def dfs(currentNode : TreeNode, level: int):

    # dict에 level 없으면 추가
    if not nodeLevel[level]:
        nodeLevel[level] = []

    # 현재 노드 값 레벨에 추가
    nodeLevel[level].append(currentNode.val)

    # 왼쪽 자식에 값 있으면 왼쪽 자식 노드 탐색
    if currentNode.left:
        dfs(currentNode.left, level + 1)

    # 오른쪽 자식에 값 있으면 오른쪽 자식 노드 탐색
    if currentNode.right:
        dfs(currentNode.right, level + 1)

Java

public void dfs(TreeNode currentNode, int level) {
		
    // map에 level 없으면 추가
    if(this.levelNode.get(level) == null) {
        this.levelNode.put(level, new ArrayList<>());
    }

    this.levelNode.get(level).add(currentNode.val); // 현재 노드 값 추가

    // 왼쪽 자식 노드 있을 경우
    if(currentNode.left != null) {
        dfs(currentNode.left, level + 1);
    }

    // 오른쪽 자식 노드 있을 경우
    if(currentNode.right != null) {
        dfs(currentNode.right, level + 1);
    }
}

 

 위 같이 구현하면 시간 복잡도는 노드개수인  O(n)만큼 시간이 걸린다. tree 자료 구조에 대한 개념만 알면 문제푸는데는 지장이 없다.

Code

Python

from collections import defaultdict

class Solution:
    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        nodeLevel = defaultdict(list)

        def dfs(currentNode : TreeNode, level: int):

            if not nodeLevel[level]:
                nodeLevel[level] = []

            nodeLevel[level].append(currentNode.val)

            if currentNode.left:
                dfs(currentNode.left, level + 1)

            if currentNode.right:
                dfs(currentNode.right, level + 1)

        dfs(root, 0)

        maxLevel = max(nodeLevel.keys())

        result = sum(nodeLevel[maxLevel])

        return result

Java

import java.util.*;

class Solution {
    Map<Integer, List<Integer>> levelNode;// levelDeep : {nodes....}
	
	public int deepestLeavesSum(TreeNode root) {
		
		this.levelNode = new HashMap<>();
		
		
		dfs(root, 0);
		
		// 가장 깊은 노드 레벨
		int maxLevel = levelNode.keySet().stream()
				.max(Integer::compare).get();
		
		// 가장 깊은 레벨 합
		int result = levelNode.get(maxLevel).stream()
				.reduce(0, (a, b) -> a + b);
		
		return result;
    }
	
	// 노드 탐색
	public void dfs(TreeNode currentNode, int level) {
		
		// map에 level 없으면 추가
		if(this.levelNode.get(level) == null) {
			this.levelNode.put(level, new ArrayList<>());
		}
		
		this.levelNode.get(level).add(currentNode.val); // 현재 노드 값 추가
		
		// 왼쪽 자식 노드 있을 경우
		if(currentNode.left != null) {
			dfs(currentNode.left, level + 1);
		}
		
		// 오른쪽 자식 노드 있을 경우
		if(currentNode.right != null) {
			dfs(currentNode.right, level + 1);
		}
	}
}