题目描述
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.
Example1:
Example:
Given 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.
解题思路
- 首先求树的深度作为一个函数
- 然后增加一个辅助函数，这个辅助函数以根结点的左右子节点为开始，分别为左深度，右深度
- 在这些左右深度里面选择一个最大的即为最后的结果
C++代码
/**
* 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 {
public:
int depthTree(TreeNode* root){
if(root == NULL){
return 0;
}
int left = depthTree(root -> left);
int right = depthTree(root -> right);
return left > right ? left + 1 : right + 1;
}
int res = 0;
void fun_helper(TreeNode* root){
if(root == NULL){
return;
}
int left = depthTree(root -> left);
int right = depthTree(root -> right);
if(left + right > res){
res = left + right;
}
fun_helper(root -> left);
fun_helper(root -> right);
}
int diameterOfBinaryTree(TreeNode* root) {
fun_helper(root);
return res;
}
};
