LeetCode-559

题目简述

给定一个N叉树，找到其最大深度
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

TreeNode代码

class Node {
	//值
    public int val;
    //孩子结点 使用List集合存储
    public List<Node> children;

    public Node() {}

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

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

我们简单的分析一下N叉树：
N叉树存储叶子节点的方式和二叉树不同
从代码中很清除的可以看到N叉树的孩子节点用一个List集合存储。

DFS

我们可以使用深度优先搜索解决这个问题。

思路：
以二叉树为例。
我们可以递归的计算结点左子树和右子树的深度，得到较大的子树深度，然后加一，即可得到本结点的深度。

比如我们要计算根结点的深度getDepth（root），则只需要计算 Math.max(getDepth(root.left),getDepth(root.right))+1即可，而左子树的深度又又可以由左子树的左子树和右子树的最大深度加一得到，递归的解决此问题。

如果不够清晰，可看代码

代码实现：

class Solution {
    public int maxDepth(Node root) {
         return getDepth(root);

    }
	//此方法用于得到数的深度
     public int getDepth(Node root){
     //如果结点为null 则返回0
        if (root==null){
            return 0;
        }
        
        //得到子结点链表
        List<Node> nodes = root.children;
        //这个遍历用于记录子树的最大深度
        int ans = 0;
        //遍历每个结点得到具有最大深度的子结点
        for (Node n : nodes){
            ans = Math.max(ans,getDepth(n));
        }
        
        //返回结果
        return ans+1;
    }
}

BFS

广度优先搜索也是一个不错的选择

思路：

树的深度就是其对应的层数，我们可以不可以这样子，每当我们遍历一层，将让ans+1，当遍历完最后一层，ans就是我们所需要的结果。

我们利用一个队列来存储叶子节点，每次遍历一层，用一个变量来存储这一层结点的多少，当变量当前层的结点的时候，将下一层的结点存入队列，当最后队列为空时，就遍历完了所有的层数，即可得到树的层数，即树的深度。

不懂可以参考代码

代码：

class Solution {
    public int maxDepth(Node root) {
         if (root==null){
              return 0;
          }
			//用来存储结点的队列
          Queue<Node> queue = new LinkedList<>();
		//记录层数 没遍历完一层 ans+1
          int ans = 0 ;
          //将根节点加入队列
          queue.add(root);
		//当队列为空时 结束循环  每一次循环就是遍历其中的一层
          while (!queue.isEmpty()){
              //一层一层遍历
              //size 用来记录当前层 的结点个数
              int size = queue.size();
			//用while循环来控制遍历本层结点的个数
              while (size>0){
              //得到结点
                  Node node = queue.poll();
                  //得到子结点 即下一层的结点
                  List<Node> list = node.children;
                  //将结点存入队列中
                  queue.addAll(list);
                  //控制本层剩余的结点个数
                    size--;
              }
              //遍历完一层 ans+1
              ans++;
          }
          //while循环结束 则将树的所有层 都遍历过了 返回结果
          return ans;

    }
}