543. 二叉树的直径

class Solution {
    int ans = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return ans;
        }
     public int dfs(TreeNode root) {
         if(root==null)return 0;
         int r = dfs(root.right);
         int l = dfs(root.left) ;
         ans =  Math.max(ans,r+l);             //根节点点加左右
         return Math.max(1+r,1+l);             //看子节点那边比较大 就返回那个
     }
    }

最大的直径可能有三种情况：
1.在左子树内部
2.在右子树内部
3.在穿过左子树，根节点，右子树的一条路径中
设计一个递归函数，返回以该节点为根节点，向下走的最长路径
知道这个值以后
以某个节点为根节点的最长直径就是，该节点左子树向下走的最长路径 ，再加上该节点右子树向下走的最长路径
我们用一个全局变量记录这个最大值，不断更新