描述

题目描述

求给定二叉树的最大深度，

最大深度是指树的根结点到最远叶子结点的最长路径上结点的数量。

示例

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

知识点：二叉树，递归，DFS，层序遍历
难度：⭐

题解

解题思路

简单的入门题，显然求树的深度通过DFS，也可以递归求出最大深度

除了DFS，相对的还可以通过层序遍历计算深度，也需要遍历所有结点

方法一：

图解

算法流程：

• 定义递归函数功能：获取root结点的最大深度
• 递归终止条件：root为null
• 返回值：先递归左子结点，再递归右子结点，最后求出每一子树的深度的最大值

Java 版本代码如下：

import java.util.*;

public class Solution {
    // 定义递归函数功能：求出当前结点的
    public int maxDepth (TreeNode root) {
        // 递归终止
        if(root == null) {
            return 0;
        }
        // dfs，先递归左子结点，再递归右子结点，最后求出每一子树的深度的最大值
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

Python 版本代码如下：

class Solution:
    def maxDepth(self , root ):
        if not root: 
            return 0
        # 先递归左子结点，再递归右子结点，最后求出每一子树的深度的最大值
        return max(self.maxDepth(root.left),self.maxDepth(root.right))+1

复杂度分析：

时间复杂度 O(N)：计算所有结点的深度的递归需要经过每个结点
空间复杂度 O(N)：递归占用的栈空间

方法二：层序遍历

算法流程：

• 维护一个队列：每次while循环保存当前层的所有结点
• 遍历每一层，每次遍历当前层每个结点
• 每次遍历一层，计数+1

Java 版本代码如下：

import java.util.*;
public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        // 队列，每次while循环保存当前层的所有结点
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        int res = 0;
        queue.add(root);
        // 遍历每一层
        while (!queue.isEmpty()) {
            int size = queue.size();
            // 遍历当前层每个结点
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
            // 记录层数
            res++;
        }
        return res;
    }
}

复杂度分析：

时间复杂度 O(N)：平均需要遍历所有结点
空间复杂度 O(1)：用到了队列，N为队列长度