LeetCode543 Diameter of Binary Tree

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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.

Note: The length of path between two nodes is represented by the number of edges between them.

样例

1
2
3
4
5
6
7
8
9
10
Input:
Given a binary tree
1
/ \
2 3
/ \
4 5

Output:
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

思路

求二叉树的直径

普通树的直径需要两遍DFS,而二叉树因为结构特殊只需一次DFS即可

假设二叉树中共有$n$个节点,第$i$个节点的左子树树高为$l_i$,右子树树高为$r_i$,则以第$i$个节点为子树的直径$d_i = l_i + r_i $,最终整棵二叉树的直径$D = max\{d_i | i=1..n\}$

代码

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
26
27
28
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
int ans;
public:
int dfs(TreeNode* u, int dep) {
if (u == NULL) return dep - 1;
// 递归求解左子树深度及右子树深度
int l = dfs(u->left, dep + 1), r = dfs(u->right, dep + 1);
// 因为当前深度是相对于root来说的,如果相对于u来说,其左右子树树高需要减去u的深度
// 即 d = l - dep + r - dep = l + r - 2 * dep
ans = max(ans, l + r - 2 * dep);
return max(l, r);
}
int diameterOfBinaryTree(TreeNode* root) {
ans = 0;
dfs(root, 0);
return ans;
}
};
分享到 评论