题解 | #牛群的最大高度#
牛群的最大高度
https://www.nowcoder.com/practice/f745023c5ac641c9914a59377dacdacf
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整型 */ public int findMaxHeight(TreeNode root) { if (root == null) { return 0; } int leftHeight = findMaxHeight(root.left); int rightHeight = findMaxHeight(root.right); return Math.max(Math.max(leftHeight, rightHeight), root.val); } }
当我们要找出二叉树中最高的牛的高度时,我们可以采用递归的方法来解决。嗯,就像一个问题分解成更小的问题一样。我们要考虑特殊情况,就是如果当前节点是空的(也就是空节点),那么它的高度就是0。
我们会想,对于非空的节点,我们应该如何计算它的高度呢?这时候,我们就可以运用递归了。因为二叉树的高度实际上就是它的左子树高度和右子树高度中较大的那个再加上1。为什么要加1呢?因为当前节点也要算在内嘛,不然怎么算最高的牛呢?
好,现在我们的思路已经有了,我们可以开始写代码了。我们首先判断当前节点是否为空,如果是的话就返回0。如果不为空,那我们就递归地计算左子树的高度和右子树的高度,然后用 Math.max
函数比较这两个高度,再加上当前节点的值(就是这头牛的高度),就得到了当前节点的高度。最后,我们只需要对整棵二叉树进行这个计算,就能得到最高的牛的高度了。
所以,嘿嘿,就像是在牧场里,我们从根节点出发,逐步递归地计算每个节点的高度,然后在递归的过程中,每一层都比较一下,看哪头牛的高度更高,最后就找到了最高的那头牛!