每日力扣算法题（简单篇）

543.二叉树的直径

原题：

给你一棵二叉树的根节点，返回该树的?直径?。

二叉树的?直径?是指树中任意两个节点之间最长路径的?长度?。这条路径可能经过也可能不经过根节点?root?。

两节点之间路径的?长度?由它们之间边数表示。

解题思路：

树类题目通常采用递归的解法，这里我们可以将题目理解为，求和左右节点最大的高度和，首先将假设只有四个节点：

我们先将问题分解为一个个子问题，先递下去，先向左遍历，从1到2再到4，发现4左右节点均为空，其左右节点返回0，归上去，节点4返回1高度，归到2节点处，由于左侧已经归了上来，则开始遍历右侧，发现右侧为空，返回0，求取左右的最大高度，结果为1，再加上该节点本身的高度，向上归，返回2，回到节点1，节点1再重复节点2的操作，返回最终结果4

顺着该思路我们便有如下代码

源代码：

int highsum(struct TreeNode* root,int maxlen,int *maxans)
{
    if(!root)
    {
        return 0;
    }
    int left_hight=highsum(root->left,maxlen,maxans)+1;
    int right_hight=highsum(root->right,maxlen,maxans)+1;
    maxlen=fmax(left_hight,right_hight);
    *maxans=fmax(*maxans,right_hight+left_hight-2);
    return maxlen;
}
int diameterOfBinaryTree(struct TreeNode* root) {
    int ans=0;
    highsum(root,0,&ans);
    return ans;
}