二叉树深度递归与非递归

二叉树的最大深度

下面给出递归算法，非递归只需要在层序遍历的基础上进行改造就可以了。

    public int maxDepth(TreeNode root) {
            if(root == null){
                return 0;
            }
            if(root.right == null){
                return maxDepth(root.left) + 1;
            }
            if(root.left == null){
                return maxDepth(root.right) + 1;
            }
            
            return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
    }

二叉树的最小深度

• 递归

        public int MinDepth(TreeNode root) {
            if(root == null){
                return 0;
            }
            if(root.left == null){
                    return MinDepth(root.right) + 1;
                }
                if(root.right == null){
                    return MinDepth(root.left) + 1;
                }

            return Math.min(MinDepth(root.left),MinDepth(root.right)) + 1;
        }

• 非递归
  还是基于层序遍历，加一个depth变量，中间过程遇到叶子节点了直接return depth

    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 1;
        while(!queue.isEmpty()){
            int l = queue.size();
            while(l -- > 0){
                TreeNode node = queue.poll();
                if(node.left == null && node.right == null){
                    return depth;
                }
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }
            depth ++;
        }        
        return depth;
    }

N叉树的最大深度

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