题解 | #牛群的最长距离#
牛群的最长距离
https://www.nowcoder.com/practice/82848c6aa1f74dd1b95d71f3c35c74d5
考察知识点:二叉树、后序遍历、递归
解题思路:这道题和`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; } }