《电子商务网站开发实训》总结外链工厂 外链

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;
}