【每日leetcode】23.二叉树的最大深度

今天又是开心的一天 ——leetcode此题热评

前言

哈喽，大家好，我是一条。

糊涂算法，难得糊涂

Question

104. 二叉树的最大深度

难度：简单

给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例：给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

Solution

为大家简答介绍两个搜索算法：DFS和BFS

DFS:深度优先搜索算法，步骤为：1.递归下去 2.回溯上来 顾名思义，深度优先，则是以深度为准则，先一条路走到底，直到达到目标。这里称之为递归下去。否则既没有达到目标又无路可走了，那么则退回到上一步的状态，走其他路。这便是回溯上来。

BFD:广度优先算法

广度优先搜索较之深度优先搜索之不同在于，深度优先搜索旨在不管有多少条岔路，先一条路走到底，不成功就返回上一个路口然后就选择下一条岔路，而广度优先搜索旨在面临一个路口时，把所有的岔路口都记下来，然后选择其中一个进入，然后将它的分路情况记录下来，然后再返回来进入另外一个岔路，并重复这样的操作。

本题就是基于深度优先搜索的递归：

• 根节点为空直接返回
• 节点为空时说明高度为 0，所以返回 0；节点不为空时则分别求左右子树的高度的最大值，同时加1表示当前节点的高度，返回该数值。

Code

所有leetcode代码已同步至github 欢迎star

/**
 * @author yitiaoIT
 */

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

Result

复杂度分析

• 时间复杂度：O(N)