leetcode559-N叉树的最大深度

原题

给定一个 N 叉树,找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

例如,给定一个 3叉树 :

leetcode559-N叉树的最大深度

我们应返回其最大深度,3。

说明:

  1. 树的深度不会超过 1000
  2. 树的节点总不会超过 5000

解法

思想

  1. 自底向上,每个节点是所有孩子节点的深度的最大值+1
  2. 自顶向下,依次更新最大高度

代码

自底向上:

class Solution {
    public int maxDepth(Node root) {
        return depth(root,0);
    }
    public int depth(Node root,int depth){
        if(root == null) return depth;
        int max = 0;
        for(Node node:root.children){
            int level = depth(node,depth+1);
            if(level>max) max = level;
        }
        return max+1;
    }
}

自顶向下:

class Solution {
    int depth = 0;
    public int maxDepth(Node root) {
        depth(root,1);
        return depth;
    }
    public void depth(Node root,int cur){
        if(root == null) return;
        if(cur>depth) depth = cur;
        for(Node node:root.children)
            depth(node,cur+1);
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode559-n%e5%8f%89%e6%a0%91%e7%9a%84%e6%9c%80%e5%a4%a7%e6%b7%b1%e5%ba%a6/