【leetcode】559 N叉树的最大深度（DFS+BFS两种解法）

我不是女神ヾ 2021-10-03 02:08 227阅读 0赞

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

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

例如，给定一个 3叉树 :

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

说明:

树的深度不会超过 1000。  
树的节点总不会超过 5000。

DFS

/*
    // 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) {
            if(root == null)
                return 0;//条件1
            int max = 0;
            for(Node cur:root.children){
                int depth = maxDepth(cur);
                max = Math.max(max,depth);
            }
            return max+1;//递归结束条件2    
        }
    }

BFS

/*
    // 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) {
            if(root == null)
                return 0;
            int max = 0;
            Queue<Node> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                int size = queue.size();
                max++;
                while(size>0){
                    size--;
                    Node cur = queue.poll();
                    for(Node curr:cur.children){
                        queue.offer(curr);
                    }
                }
            }   
            return max;
        }
    }