题目：
543.Diameter of Binary Tree(easy)
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.
Example:1
2
3
4
5
6
7Given a binary tree
1
/ \
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
Note: The length of path between two nodes is represented by the number of edges between them.
题目大意：
给定一个二叉树，找出任意两个节点中的最长距离。
解题思路：
这题本质上也是二叉树深度的应用，任意两个节点间的最长路径必定是以某个节点为根节点的左右子树高度之和。
如果不是，则一定在一个子树上，也可看成所在的另一子树为空的情况，也可概括成以上情况。
则最长路径max(Len) = max(len,L + R);
注意，递归时返回时格式几乎固定为max(L,R) + 1，否则无法迭代出高度。
具体的讲解还可以看这个：B站 Leetcode543，讲的非常清晰，而且说明了“两个节点的最大长度不一定要过根节点”的情况。
还有一个讲解【HOT 100】9.二叉树的直径 Python3 递归也需要看清题意 这里面也讲到了不能一看到树就无脑递归模板。。
注意：！！！我们常用方法计算一个节点的深度：max(length(node.left),length(node.right)) + 1 ！！！
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26Java:
public int diameterOfBinaryTree(TreeNode root){
int[]ans = new int[1];
//这是Java中数组的动态初始化写法，int型数组元素默认为0
getLength(root,ans);
return ans[0];
}
//所有与二叉树高度有关的问题都可以从这个写法上去改
private int getLength(TreeNode root，int[] ans){
if(root == null) return 0;
int L = getLength(root.left,ans);
int R = getLength(root.right,ans);
ans[0] = Math.max(ans[0],L+R);
return Math.max(L,R) + 1;
/*这个地方写成Math.max(getLength(root.left,ans),getLength(root.right,ans)) + 1的话，
会报 超出时间限制的错误。估计是多层递归栈的深度太大，
时间就超了
*/
}
Python:
