题目如下：

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:
Given a binary tree 

1
2
3
4
5
    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.

题目大意

给定一颗二叉树，寻找这棵树的直径，直径定义为这棵树中任意两个节点的路径长度最大值。如上面的给定的那棵树，明显最长路径是3，也即4 -> 2 -> 1 -> 3。当然有一点要注意，最长路径可能不经过根节点。

思路

这道题是104. Maximum Depth of Binary Tree的运用题目。刚拿到题目我一开始是不敢做的， 因为潜意识里认为这题很难。但是看了一下题目居然是Easy难度，仔细思考了一下发现难度其实不大，主要是考查树的遍历。最长路径有两种：

其一，这条路径经过了根节点，那么只需要找出根节点下的两棵子树的深度然后相加即可。

其二，如果这条路径没有经过根节点，那么只需要找出根节点左子树内或者根节点右子树内的最深度即可。自底向上，递归查找子树的深度，如果发现左子树深度与右子树深度之和大于当前纪录的直径，那么进行相应的值记录，然后返回左子树和右子树深度较大的那个来进行下一轮的比对。递归完成之后即可找出直径。

整个树进行了一次递归调用，因此时间复杂度是O(n)，n是树的节点数，同时，只使用了一个数来记录直径，因此空间复杂度是O(1)，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int depth = 0;
public int diameterOfBinaryTree(TreeNode root) {
    search(root);
    return depth;
}

private int search(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = search(root.left);
    int right = search(root.right);
    if (depth < left + right) {
        depth = left + right;
    }
    return left > right ? left + 1 : right + 1;
}

提交AC，运行时间8ms

提交结果
提交结果

总结

其实很多题目并不难，只是自己看到题目之后觉得比较复杂，潜意识里就认为这道题比较难而不敢做。这道题只是之前做过的一道题的扩展而已，继续加油练习。