LeetCode 543. 二叉树的直径
原题链接
简单
作者:
linux_2019
,
2019-10-03 07:30:44
,
所有人可见
,
阅读 987
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:
map<TreeNode * ,int> d;
int ans;
void dp(TreeNode * root)
{
if(!root->left&& !root->right) return ;
if(root->left)
{
dp(root->left);
ans=max(ans,d[root]+d[root->left]+1);
d[root]=max(d[root],d[root->left]+1);
}
if(root->right)
{
dp(root->right);
ans=max(ans,d[root]+d[root->right]+1);
d[root]=max(d[root],d[root->right]+1);
}
}
int diameterOfBinaryTree(TreeNode* root) {
if(!root) return 0;
ans=0;
dp(root);
return ans;
}
};