559 : Maximum Depth of N-ary Tree ( leetcode / java )

 

*해결 과정

먼저 기본적으로 주어진 Node 의 형태를 확인해보자.

class Node

 

  N차 노드이기 때문에 자손이 List<Node>로 선언되었다는 것에 유의한다. 특히 우리는 depth를 구해야 하는데, Node에는 depth 변수가 선언되있지 않기 때문에 별도의 변수 선언이 필요하다. 여기서 해결 방안은 2가지이다.

 

1. 새로운 class를 만들어 depth를 추가한다.

2. depth에 대한 전역변수를 만들고 계속 업데이트하면서 값을 구한다.

 

 

*1번

class Point{
    Node node;
    int depth;
    public Point(Node node, int depth){
        this.node=node;
        this.depth=depth;
    }
}

class Solution {
    
    int ans=0;
    public int maxDepth(Node root) {
        if(root==null) return 0;
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(root,1));
        while(!queue.isEmpty()){
            Point point = queue.poll();
            int depth = point.depth;
            if(depth>ans) ans=depth;
            for(int i=0;i<point.node.children.size();i++){
                Node childrenNode = point.node.children.get(i);
                queue.add(new Point(childrenNode,depth+1));
            }
        }
        return ans;
    }
}

 

*결과

  내가 짠 코드는 생각보다 Runtime에서 효율이 좋지 않다. 아마 새로운 class를 선언하고 작업하는 과정에서 많은 시간이 소모된 것으로 예상된다.

 

 

*2번

class Solution {
    
    int res=0;
    
    public int maxDepth(Node root) {
        
        if(root==null) return 0;
        return helper(root);
    }
    public int helper(Node root){
        if(root.children.size()==0) return 1;
        
        int localMax=0;
        for(Node child : root.children){
            localMax = Math.max(localMax,helper(child)); 
        }
        
        return 1+localMax;
    }
}

 

*결과

 

 

  새로운 class를 만들지 않고 depth의 변수만 만들어주고 계속 재귀를 돌면서 업데이트를 한다. helper 재귀는 계속 자식으로 재귀를 들어가 맨 마지막 leaf노드에 도달한다. 보통 root==null를 통해 해당 노드가 마지막임을 구분하는데, 여기는 List<Node> children으로 선언되어 있기 때문에 size()로 리프노드를 구분한다. 이후 계속 +1씩 업데이트하면서 depth가 결정되고,  Math.max(localMax,helper(child))를 통해 현재 같은 레벨의 자손 중에 최대의 depth를 업데이트하여 다시 부모에 depth+1로 반환한다.