题目描述
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.
递归版本解题思路
- 直径为：求二叉树的一个点到另一个点最长的路径
- 求出以当前节点为中心，左子树+右子树的高度
- 然后递归求出当前节点的左子节点，当前节点的右子节点，看哪个大，（经过根节点的直径不一定是最大的）
/**
* 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 res = 0;
int diameterOfBinaryTree(TreeNode* root) {
if(root == NULL){
return 0;
}
int res = treeDepth(root -> left) + treeDepth(root -> right);
return max(res, max(diameterOfBinaryTree(root -> left), diameterOfBinaryTree(root -> right)));
}
int treeDepth(TreeNode* root){
if(root == NULL){
return 0;
}
int left = treeDepth(root -> left);
int right = treeDepth(root -> right);
return left > right ? left + 1 : right + 1;
}
};
0305递归版本解题思路
- 最后递归求最大的时候，应该是比较经过当前root，未经过当前max(left + right, max(root -> left), max(root -> right))
