99클럽 코테 스터디 13일차 TIL Deepest Leaves Sum

 

 

자료구조 이진트리(Binary Tree) 그림으로 쉽게 이해하기

 

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

 

 

1. 문제 및 접근

 

1302 leetcode

 

이진 탐색트리의 가장 깊은 리프의 값들의 합을 반환

 

그림과 예제가 처음에 이해가지 않았다 내가 생각하는 이진탐색트리는 막연하게 완전이진트리로 생각해서

수가 들어가는 예제에서 헤맸지만, 그냥 각 노드에서 최대 2개까지 가지고 있는 기본 이진트리를 말하는 것

들어온 input대로 그냥 채워주면 되는 것이다!

 

먼저 채워진 트리에서 dfs나 bfs로 탐색해 제일 깊은 레벨의 수 세어주기 ( 어차피 끝까지 돌아야해서 아무거나 해도 될듯)

 

 

제한사항

 

• 노드의 수 범위는 1~10,000
• 수는 1~100

 

 

 

2. 이진트리 Binary Tree

 

 

https://rosweet-ai.tistory.com/55

 

 

 

 

이진트리는 여러 종류가 있는데 Binary Tree 자체를 Binary Search Tree 로만 받아 드려서 문제 input을 넣는 과정에서 시간을 많이 허비했다.

 

 

2-1 이진탐색트리 (Binary Search Tree)

 

 

 

이진 탐색 트리는 어떠한 값을 찾는것에 특화된 자료구조이고,
즉, '이진 탐색'을 위한 트리이자, 탐색을 위한 '이진 트리'라는 뜻

(이진탐색트리는 이진트리지만 이진트리는 이진탐색트리가 아니다)

 

이진 탐색 트리는 이진 트리와 별반 다를게 없지만, 특수한 규칙이 있는데.

 

"왼쪽 자식 노드는 나보다 작고, 오른쪽 자식 노드는 나보다 크다"

 

 

 

 

 

3.풀이

 

package 알고리즘.프로그래머스.항해99.이주차;



public class DeepestLeavesSum {
    //1302 leetcode

    //이진 탐색트리의 가장 깊은 리프의 값들의 합을 반환

    //그림과 예제가 처음에 이해가지 않았다 내가 생각하는 이진탐색트리는 막연하게 완전이진트리로 생각해서
    //수가 들어가는 예제에서 헤맸지만, 그냥 각 노드에서 최대 2개까지 가지고 있는 기본 이진트리를 말하는 것
    // 들어온 input대로 그냥 채워주면 되는 것이다!

    // 먼저 채워진 트리에서 dfs나 bfs로 탐색해 제일 깊은 레벨의 수 세어주기 ( 어차피 끝까지 돌아야해서 아무거나 해도 될듯)


    int maxDepth = -1;
    int sum = 0;
    public int deepestLeavesSum(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode root, int depth) {
        if (root == null) {
            return 0;
        }
        if (maxDepth < depth) {
            maxDepth = depth;
            sum = root.val;
        } else if (maxDepth == depth) {
            sum += root.val;
        }
        if (root.left != null) {
            dfs(root.left, depth + 1);
        }

        if (root.right != null) {
            dfs(root.right, depth + 1);
        }
        return sum;
    }
    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;
      }
  }}

전체 풀이

 

 

3-1 변수 및 DFS 호출

 

 

제일 깊은 depth와 깊은 depth의 합계를 받는 변수 초기화

 

TreeNode 타입의 input을 받고, depth를 0으로 시작해 호출

 

 

 

 

3-2 DFS

 

 

재귀 함수로 구현했고,

 

root가 null 이면 바로 0 return,

 

현재의 노드의 깊이가 MaxDepth보다 클 경우 MaxDepth를 바꿔주고, 새로운 max니까 sum에 그 값 넣어주기

 

 

만약 지금 depth가 MaxDepth 라면 ?

 

sum에 현재 수를 더해줌

 

 

 

3-3 자식노드 확인

 

 

두가지 경우로,

 

현재의 자식이 왼쪽이나 오른쪽에 존재한다면 Depth를 1 늘려 재귀 호출하고

 

 

나온 sum 값을 return 해주면 끝!

 

 

 

 

4. 마무리

 

 

사실 binary Tree의 경우 많은 용어와 종류들이 있지만, 간단하고 꼭 익히고 있어야 한다..

 

대충 대충 뜻만 알고 있다가 착각하는 오류를 범해서 시간을 좀 허비했는 게 아쉽네

 

 

binary Tree의 경우 사실 데이터가 한쪽으로 쏠리거나 정렬된 상태의 데이터가 들어온다면 쓰는 이유가 없어진다..

 

그래서 균등하게 데이터를 분배하는 AVL이나, red-Black Tree를 사용하는데

 

다음에 좀 더 자세하게 공부해봐야겠다.. 

 

시간은 한정적이고, 나는 멍청하고, 범위는 방대하고...