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

题目考察的知识点 : 二叉树遍历

题目解答方法的文字分析：

本题类似于 链接NB37农场最大产奶牛群

利用深度优先算法寻找左子树和右子树的路径长度
维护最大路径max与每次选择左右子树路径和+1比较
当前节点为路径中一点情况时,返回左右路径最大值+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 {
    private int max = 0;
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型
     */
    public int diameterOfBinaryTree (TreeNode root) {
        // write code here
        if(root == null) return 0;
        getMax(root);
        return max - 1;
    }

    private int getMax(TreeNode root) {
        if (root == null) return 0;
        int left = getMax(root.left);
        int right = getMax(root.right);
        int path = left + right + 1;
        if (max < path) max = path;
        return left < right ? right + 1 : left + 1;
    }
}