Leetcode 第104题

好久没有刷题了，晋升挂了考虑换个工作了，开始刷题之路。

leetcode国内题库链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

思路分析：

本题是一道最基础的二叉树的问题。遇到二叉树的问题时，基本就是固定的套路：递归或者循环

计算二叉树的深度，简单来说就是分别计算左子树和右子树的深度，并取最大值即可

递归思路：

递归计算左右子节点直到都为空，此时记高度为1，然后不断回归到根节点，取左子树高度和右子树高度的最大值。该解法实际上就是DFS，深度优先搜索。

使用递归时，代码简洁清晰，但是在计算量大时会StackOverFlow。时间复杂度O(N),空间复杂度O(深度)

代码：

循环思路：

把每一层节点存入队列中，然后每次循环完同一层节点之后高度加一，直到到达叶子节点。此时计算得出的高度就是二叉树的深度。该解法实际上就是BFS，广度优先搜索。

时间复杂度O(N)，空间复杂度O(宽度)，最坏情况O(N)

代码：

以上就是Leetcode-104题的两个解法，算是二叉树的最基础的问题。

                                                                                                                    记录于2021-03-29