题解 | #二叉树的最大深度#

方法一（递归）

1.题意整理

• 给定一颗二叉树。
• 求二叉树的最大深度。深度是指树的根节点到任一叶子节点路径上节点的数量。

2.思路整理

按照二叉树递归的套路，需要考虑当前节点的情况、当前节点左子树的情况、当前节点右子树的情况。只要知道当前节点左右子树的深度，那么当前节点为根的子树的深度即为两者中较大的一个深度加1。

• 递归终止条件：root为空，直接返回0。
• 递归如何传递：每次需要往左右子树方向递归，只要直到左右子树深度，即可计算当前子树深度。
• 递归的返回值：返回当前子树深度。

图解展示：

3.代码实现

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        //为空，直接返回0
        if(root==null) return 0;
        //左子树深度
        int left=maxDepth(root.left);
        //右子树深度
        int right=maxDepth(root.right);
        //左右子树深度的较大者加1即为当前子树深度
        return Math.max(left,right)+1;
    }
}

4.复杂度分析

• 时间复杂度：需要遍历二叉树中所有节点，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：递归栈的深度为$lo{g}_{2}nlog\_2n$，当退化为链表时，深度为n，所以空间复杂度为$O(n)O(n)$。