543.二叉树的直径
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1：
输入：root = [1,2,3,4,5] 输出：3 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：
输入：root = [1,2] 输出：1
提示：
- 树中节点数目在范围
[1, 104]内 -100 <= Node.val <= 100
整体思路：
直径是任意两个节点之间最长路径长度，也就是左子树的最大深度+右子树的最大深度
但是本题说明：这条路径可以不经过根节点，也就是说最长的路径也是可能某个子节点的子节点们更多，这个长度就会大于路过根节点的长度，所以就取最大即可，那我们就需要一个变量来记录“每个节点的左子树最大深度+右子树最大深度”，每次都更新出来一个最大的值，所有都遍历完就是最后的直径
代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
int ans = 0;//记录最大值，也就是本题的解
public:
int dfs(TreeNode* node){
if(node == nullptr){//空节点
return -1;//递归终止条件
}
int l = dfs(node -> left) + 1;//有左节点，左深度+1
int r = dfs(node -> right) + 1;//有右节点，右深度+1
ans = max(ans,l + r);//记录并更新最大值到ans里
return max(l , r);//如果一定到有根节点的最大深度
}
int diameterOfBinaryTree(TreeNode* root) {
dfs(root);//root调用上述函数
return ans;//返回最大值
}
};