描述

求给定二叉树的最大深度，最大深度是指树的根结点到最远叶子结点的最长路径上结点的数量。

示例1

输入：
{1,2}

返回值：
2

示例2

输入：
{1,2,3,4,#,#,5}

返回值：3

思路

深度优先遍历

说白了就是去递归遍历每条到根节点的所有路径，找到最长的那个路径。

AC代码

public int maxDepth (TreeNode root) {
        // write code here
        // 如果到底了就返回 0
        if (root == null) {
            return 0;
        }
        // 左节点的最大深度
        int leftLength = maxDepth(root.left);
        // 右节点最大深度
        int rightLength = maxDepth(root.right);
        // 加上当前节点的长度 1
        return Math.max(leftLength, rightLength) + 1;
    }

• 时间复杂度：O(n)，n 为二叉树的节点数量，因为每个节点都会被遍历到。
• 空间复杂度：O(h), h 为二叉树的高度，递归会占用栈空间。

广度优先遍历

广度优先比哪里就是横向遍历，一层一层的来, 统计其层数，因为层数 == 二叉树的最大深度。

AC代码

public int maxDepth (TreeNode root) {
        // write code here
        // 如果到底了就返回 0
        if (root == null) {
            return 0;
        }
        // 最大深度，其实就是二叉树的层数
        int res = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i ++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }

            }
            // 层数 ++
            res ++;
        }
        return res;
    }

• 时间复杂度：O(n)，n 为二叉树的节点数量，因为每个节点都会被遍历到。
• 空间复杂度：O(n), n 为二叉树的节点数量，最坏的情况是每一层一个节点。

最后

大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索：【蘑菇睡不着】交个朋友～
也可以扫描下方二维码。