Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
1 diameter可能存在三个地方,一个是在左子树,一个在右子数,一个经过根节点
2 这种问题一般用递归来实现
3 根节点为root的二叉树的直径=max(左子树直径,右子树直径,左子树最大深度(不包括根节点)+右子树最大深度(不包括根节点)+1)
4 这里深度和路径的概念是不一样的
5 对于每一个节点,通过这个节点的直径=左子树的最大深度+右子树的最大深度
6 深度是节点数
7 全局变量会追踪最长path
1 刷这么多遍还是出错!!!
每次返回时count的edge是其上面的edge,因为比如count叶子节点的edge,就是其上面的。所以在写上面的code时,直接是left+right就行了