题解 | #判断是不是平衡二叉树#
判断是不是平衡二叉树
https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222
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 pRoot TreeNode类 * @return bool布尔型 */ public boolean IsBalanced_Solution (TreeNode pRoot) { // write code here //遍历到叶子节点判断高度差是否超过1 if(pRoot==null){ return true; } int ls = sum(pRoot.left); int rs = sum(pRoot.right); if(ls-rs>1||rs-ls>1){ return false; } // 根节点是平衡的 //那么对于左右子树必须平衡; return IsBalanced_Solution(pRoot.left)&& IsBalanced_Solution(pRoot.right); } //统计子树的深度 public int sum(TreeNode pRoot){ if(pRoot==null){ return 0; } if(pRoot.left==null&&pRoot.right==null){ return 1; } int ls =sum(pRoot.left); int rs = sum(pRoot.right); //子节点深度加本身 return ls>rs ?ls+1:rs+1; } }