Leetcode
2020.04.30 11:59

559. Maximum Depth of N-ary Tree

조회 수 291 추천 수 0 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 첨부
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 첨부

Given a n-ary tree, find its maximum depth.

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

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

 

Example 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: 3

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: 5

 

Constraints:

  • The depth of the n-ary tree is less than or equal to 1000.
  • The total number of nodes is between [0, 10^4].


/*
// 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;
    }
};
*/

class Solution {
    public int maxDepth(Node root) {
        Queue<Node> queue = new LinkedList<>();
        int depth = 0;
        
        if(root == null){
            return depth;
        }
        
        queue.offer(root);
        
        while(queue.size() > 0){
            int size = queue.size();
            for(int i=0; i<size; i++){
                Node node = queue.poll();
                for(int j=0; j<node.children.size(); j++){
                    queue.offer(node.children.get(j));
                }
            }
            depth++;
        }
        
        return depth;
    }
}


/*
// 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;
    }
};
*/

class Solution {
    public int maxDepth(Node root) {
        return findDepth(root, 1);
    }
    
    public int findDepth(Node node, int depth){
        if(node == null){
            return depth - 1;
        }
        
        if(node.children == null || node.children.size() == 0){
            return depth;
        }
        
        int[] depths = new int[node.children.size()];
        for(int i=0; i<depths.length; i++){
            depths[i] = findDepth(node.children.get(i), depth + 1);
        }
        
        Arrays.sort(depths);
        
        return depths[depths.length-1];
    }
}


[문제] https://leetcode.com/problems/maximum-depth-of-n-ary-tree/



?

List of Articles
번호 분류 제목 글쓴이 날짜 조회 수
57 Leetcode 671. Second Minimum Node In a Binary Tree hooni 2020.05.01 364
56 Leetcode 669. Trim a Binary Search Tree hooni 2020.05.01 250
55 Leetcode 110. Balanced Binary Tree hooni 2020.05.01 256
54 Leetcode 257. Binary Tree Paths hooni 2020.05.01 237
53 Leetcode 112. Path Sum hooni 2020.05.01 241
52 Leetcode 108. Convert Sorted Array to Binary Search Tree hooni 2020.05.01 228
51 Leetcode 1108. Defanging an IP Address hooni 2020.05.01 235
50 Leetcode [todo] 687. Longest Univalue Path hooni 2020.05.01 238
49 Leetcode 111. Minimum Depth of Binary Tree hooni 2020.04.30 238
» Leetcode 559. Maximum Depth of N-ary Tree file hooni 2020.04.30 291
47 Leetcode 993. Cousins in Binary Tree file hooni 2020.04.30 256
46 Leetcode 690. Employee Importance hooni 2020.04.30 240
45 Programmers team game secret hooni 2020.04.30 0
44 Programmers fib secret hooni 2020.04.30 0
43 Programmers hashmap secret hooni 2020.04.30 0
42 Leetcode 107. Binary Tree Level Order Traversal II hooni 2020.04.29 251
41 Leetcode 459. Repeated Substring Pattern hooni 2020.04.28 238
40 Leetcode 1122. Relative Sort Array hooni 2020.04.28 261
39 Leetcode 412. Fizz Buzz hooni 2020.04.28 269
38 Leetcode 202. Happy Number hooni 2020.04.28 253
Board Pagination Prev 1 2 3 4 Next
/ 4