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

考察知识点：二叉树、后序遍历、递归

解题思路：这道题和`NB37 农场最大产奶牛群`基本是同一道题，只不过一个是求总和一个是求路径。具体思路就是使用一个全局变量存储最长距离，同时采用后续遍历的方式，分别求得左子树和右子树的最大深度，再加上1得到当前节点的最大距离，同时将这个最大距离与全局最大距离比较，如果大于则将全局的替换。遍历完整个树，全局最长距离也就更新完成了。

本题解所用语言：java

具体代码如下：

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 {
    int maxLen = 0;
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型
     */
    public int diameterOfBinaryTree (TreeNode root) {
        // write code here
        if (root == null) {
            return 0;
        }
        dfs(root);
        return maxLen - 1;
    }

    public int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = dfs(root.left);
        int right = dfs(root.right);
        int sum = left + right + 1;
        if (sum > maxLen) {
            maxLen = sum;
        }
        return Math.max(left, right) + 1;
    }
}