来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

题目描述

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

题目分析

提供两种方法实现：

• BFS（Breath First Search）广度优先搜索
• DFS（Deep First Search）深度优先搜索

代码实现

public class MaxDepth104 {


    public static void main(String[] args) {
        MaxDepth104 maxDepth = new MaxDepth104();
        TreeNode root = new TreeNode(1, new TreeNode(10), new TreeNode(2, new TreeNode(3), new TreeNode(9, null, new TreeNode(4))));
        maxDepth.maxDepth(root);
        maxDepth.maxDepth2(root);
    }


    /**
     * 广度优先算法
     *
     * @param root
     * @return
     */
    public int maxDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int depth = 0;
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);

        while (!queue.isEmpty()) {

            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                if(curr.left != null){
                    queue.offer(curr.left);
                }
                if(curr.right != null){
                    queue.offer(curr.right);
                }
            }

            depth++;
        }

        return depth;
    }

    /**
     * 前序遍历  深度优先算法
     * <p>
     * 时间复杂度：O(n)，其中 nnn 为二叉树节点的个数。每个节点在递归中只被遍历一次。
     * <p>
     * 空间复杂度：O(height)，其中 height\textit{height}height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。
     *
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

        int maxDepth = Math.max(leftDepth, rightDepth) + 1;
        System.out.println(maxDepth);
        return maxDepth;
    }


}

BFS复杂度

• 时间复杂度：O(n)
• 空间复杂度：此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到 O(n)

DFS复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(height)，其中 height 表示二叉树的高度

好了，今天就到这里，感谢各位看官到这里，不如点个关注吧！