题解 | #牛群的最长距离#

1. 题目考察的知识点

二叉树的遍历

2. 题目解答方法的文字分析

一条路径的长度为该路径经过的节点数减一.则牛群的最长距离为该路径上的节点数减一。而一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。 深度优先遍历, 递归找到每个节点左右子树的最大深度之和，找出最大那一个即可。

3. 本题解析所用的编程语言

java

4. 完整且正确的编程代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
     int ans = 0;
    public int diameterOfBinaryTree (TreeNode root) {
        dfs(root);
        return ans ;
    }
    int dfs(TreeNode root){
      if(root==null){
        return -1;
      }

      int left = dfs(root.left)+1;//左子树的最大路径长度
      int right = dfs(root.right)+1;//右子树的最大路径长度
      ans = Math.max(ans,left+right);//左右最大路径拼接而成二叉树的最大路径长度
      return Math.max(left,right);//当前子树的最大路径
    }
}