题目如下:

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

提交结果
提交结果

总结

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