题目来源

559. N叉树的最大深度

题目解析

层次遍历

class Solution {
    public int maxDepth(Node root) {
        if (root == null){
            return 0;
        }
        int ans = 0;
        LinkedList<Node> list = new LinkedList<>();
        list.offer(root);
        while (!list.isEmpty()){
            int size = list.size();
            LinkedList<Node> tmp = new LinkedList<>();
            for (int i = 0; i < size; i++){
                Node pop = list.pop();
                for (Node child : pop.children){
                    tmp.offer(child);
                }
            }
            list = tmp;
            ans++;
        }
        return ans;   
    }
}

在这里插入图片描述

递归

首先来看一种常见的递归解法，就是需要有一个当前深度，然后带一个全局变量res进去。在递归函数中，如果node为空，直接返回。若子结点数组为空，那么结果res和cur比较取较大值。否则就遍历子结点数组，对每个子结点调用递归函数，这里的cur要自增1

class Solution {
    private int ans = 0;
    public int maxDepth(Node root) {
        helper(root, 1);
        return ans;
    }
    private void  helper(Node root, int depth){
        if (root == null){
            return;
        }
        if (root.children.isEmpty()){
            ans = Math.max(ans, depth) ;
        }
        for (Node child: root.children) {
            helper(child, depth + 1);
        }
    }
}

解法2

public int maxDepth(Node root) {
        if (root == null){
            return 0;
        }
        int ans = 0;
        for (Node child : root.children){
            ans = Math.max(ans, maxDepth(child));
        }
        return ans + 1;
    }

直接主函数中递归，首先判空，否则就是遍历子结点数组，然后对每个子结点调用递归函数的返回值加1后跟res相比，取较大值更新结果res

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