[LeetCode] 559. Maximum Depth of N-ary Tree (easy)

https://leetcode.com/problems/maximum-depth-of-n-ary-tree/

Maximum Depth of N-ary Tree - LeetCode

Point1 . 이진트리의 최대 높이를 구하는 문제이다.

 

Point2. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

-> 최대 높이는 루트 노트와 가장 먼 리프 노드의 거리라고 한다.

 

Point3. 따라서, Example을 보면 알 수 있듯이 최상단 루트 노드의 레벨은 1이 될 것이다.

 

Point4. BFS방식으로 1depth를 돌 때마다 레벨을 증가시키면 된다.

 

Point5. 큐를 이용하여 1depth 전체를 넣고 빼준다.

 

public class MaximumDepthofNaryTree {
    public int maxDepth(Node root) {
        int rtn = 0;
        if(root == null) return rtn;

        Queue<Node> que = new LinkedList<>();
        que.offer(root);    //1. 처음엔 최상단 루트 1이 들어온다.

        while(!que.isEmpty()) {
        	rtn++;  //큐가 생성될 때마다 레벨 상승
        
            int size = que.size();
            for(int i = 0; i < size; i++) {
                Node node = que.poll();	//2. que에 빼준 1node를 node객체에 넣기(==current node)
                
                //3. 1node의 자식들을 비어 있는 큐에 다 넣어준다.
                for(Node child : node.children) {
	                //4. 큐가 채워졌다.
                    que.offer(child);	
                }
/* 1node의 자식들은 3,2,4이므로 3번 반복하면서 각 노드를 빼고 그 자식 노드들을 큐에 다시 넣어주는걸 반복한다. */
            }
        }

        return rtn;
    }

    // Definition for a Node.
    class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }
}

BFS를 이용한 이진트리 탐색의 기본 문제이기 때문에,

 

이런 문제는 확실히 이해하고 풀 수 있을 정도로 훈련해야 한다.