LeetCode - Easy - 559. Maximum Depth of N-ary Tree

清疚 2022-10-06 00:50 13阅读 0赞

## Topic ##

*  Tree
 *  Depth-first Search
 *  Breadth-first Search

## Description ##

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

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:**

![042aa242e9be82786f7906e8d95631bb.png][]

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

**Example 2:**

![481a463e68315c2a1a14ec0d9522c4dd.png][]

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 , 1 0 4 \] \[0, 10^4\] \[0,104\].

## Analysis ##

方法一：DFS + Java8

方法二：BFS

方法二：DFS

## Submission ##

import java.util.LinkedList;
    
    import com.lun.util.NAryTree.Node;
    
    public class MaximumDepthOfNAryTree { 
    	
    	//方法一：DFS + Java8
        public int maxDepth(Node root) { 
            int max = 0;
        	if(root == null) return max;
        	
            if(root.children != null)
            	max = root.children.stream().map(a->maxDepth(a))//
            		.max((a1, a2)->a1-a2).orElse(0);
        	
        	return max + 1;
        }
    	
        
        //方法二：BFS
        public int maxDepth2(Node root) { 
        	if(root == null) return 0;
        	LinkedList<Node> queue = new LinkedList<>();
        	queue.offer(root);
        	int depth = 0;
        	while(!queue.isEmpty()) { 
        		depth++;
        		for(int size = queue.size(); size > 0; size--) { 
        			Node node = queue.poll();
        			if(node.children != null)
        				queue.addAll(node.children);
        		}
        	}
        	return depth;
        }
        
        //方法三：DFS
        public int maxDepth3(Node root) { 
        	if(root == null) return 0;
        	
        	int max = 0;
            if(root.children != null) { 
            	for(Node node : root.children) { 
            		int temp = maxDepth3(node);
            		max = Math.max(max, temp);
            	}
            }
        	return max + 1;
        }
        
    }

## Test ##

import static org.junit.Assert.*;
    import static com.lun.util.NAryTree.*;
    
    import org.junit.Test;
    
    import com.lun.util.NAryTree.Node;
    
    
    public class MaximumDepthOfNAryTreeTest { 
    
    	@Test
    	public void test() { 
    		MaximumDepthOfNAryTree obj = new MaximumDepthOfNAryTree();
    
    		Node root = integersToNAryTree(1,null,3,2,4,null,5,6);
    		assertEquals(3, obj.maxDepth(root));
    		assertEquals(3, obj.maxDepth2(root));
    		assertEquals(3, obj.maxDepth3(root));
    		
    		Node root2 = integersToNAryTree(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);
    		assertEquals(5, obj.maxDepth(root2));
    		assertEquals(5, obj.maxDepth2(root2));
    		assertEquals(5, obj.maxDepth3(root2));
    	}
    	
    }

[https_leetcode.com_problems_maximum-depth-of-n-ary-tree]: https://leetcode.com/problems/maximum-depth-of-n-ary-tree/
[042aa242e9be82786f7906e8d95631bb.png]: /images/20221005/6fd2875c9b934ae480a4d1ac445f9d00.png
[481a463e68315c2a1a14ec0d9522c4dd.png]: /images/20221005/16ffd984b51f452e87b65c6d49fead14.png