기억하고싶은것들

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.
Return the smallest level x such that the sum of all the values of nodes at level x is maximal.

이진트리의 루트가 주어지고, 루트의 레벨은 1이고, 루트의 자식의 레벨은 2이고 그 하위도 레벨이 1식 증가한다.

동일 레벨의 값 합이 가장 큰 레벨을 리턴하라, 단 가장 작은 레벨을 리턴하라. 

트리의 레벨별로 값의 합을 구하면 되므로 bfs를 이용하여 해답을 구해보자.

bfs는 Queue 자료구조를 사용하여 구현가능하다.

    public int maxLevelSum(TreeNode root) {
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        int level = 0;
        int minLevel = 0, maxSum = Integer.MIN_VALUE;
        while (!queue.isEmpty()) {
            int size = queue.size();
            level++;
            int levelSum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                levelSum += node.val;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);

            }
            if (levelSum > maxSum) {
                maxSum = levelSum;
                minLevel = level;
            }
        }
        return minLevel;
    }

문제 출처 : 

leetcode.com/problems/maximum-level-sum-of-a-binary-tree/

• BFS의 개념
• BFS에 대한 간단한 코드 설명 
• BFS의 장단점
• LeetCode 예시 문제 및 참고 코드

BFS ( Breadth First Search )는 너비 우선 탐색이라 불리는 알고리즘이다.

해당 알고리즘은 보통 DFS ( Depth First Search)와 많이 비교 된다. 

두 알고리즘은 모두 그래프를 탐색하는데 많이 사용된다.

그래프 탐색이란 - 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

예를 들어, 특정 도시에서 다른 도시로 이동을 할 수 있는지 탐색하는 것이 될 수 있다.

BFS는 그래프를 탐색시, 너비를 우선 해서 탐색을 하겠다는 전략이다. 

즉, 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법을 말한다.

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.

사용하는 경우는 보통 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

위의 설명을 코드로 나타낸 간단한 의사 코드를 보면 아래와 같을 수 있다. 

void search(Node root) {
  Queue queue = new Queue();
  root.marked = true; // (방문한 노드 체크)
  queue.enqueue(root); // 큐에 추가

  // 큐가 소진될 때까지 반복한다.
  while (!queue.isEmpty()) {
    Node r = queue.dequeue(); // 큐에서 노드 추출
    r.marked = true; // (방문한 노드 체크)
    
    // 큐에서 꺼낸 노드와 인접한 노드들을 모두 차례로 방문한다.
    foreach (Node n in r.adjacent) {
      if (n.marked == false) {
        queue.enqueue(n); // 큐에 추가
      }
    }
  }
}

BFS의 장단점은 아래와 같을 수 있다

• 장점
  • 출발 노드로 부터 목표 노드까지의 최단 경로를 보장해 준다.
• 단점
  • BFS에 비해 코드 구현이 까다롭다.
  • Queue에 노드를 저장하다 보니, 저장공간이 준비되어있어야 한다. 

예시 문제 

1161 - Maximum Level Sum of a Binary Tree ( 이진트리의 합이 가장 큰 레벨 )

joomn11.tistory.com/37

513 - Find Bottom Left Tree Value ( 트리의 가장 밑의 왼쪽 값 찾기 )

joomn11.tistory.com/39

429 - N-ary Tree Level Order Traversal ( N-ary 트리의 레벨 순서 순회 )

joomn11.tistory.com/38