20200310
Plan
- LeetCode 45mins 实际1小时
Notes
LeetCode 543. 二叉树的直径
核心思想
- 对根节点，获取左子树深度ld
- 对根节点，获取右子树深度rd
- 将ld + rd作为这个节点作为根节点时，可以获得的最大直径
- 同样方法获取左右节点的最大直径，取最大值
实际编码
我的实现方式为两层递归，最外层递归，用于dfs搜索整个树，在每个节点上用递归获取左右子树的深度。
然而，看答案中，解法明显更好，具体的改进为：
- 设定一个全局变量用于记录以其为根的最大宽度
- 在计算深度的递归函数中，没到一个节点，刷新全局变量
很简单的算法时间复杂度就从 N^2 变成了 N。
More
熟能生巧