题解 | #判断是不是平衡二叉树#
判断是不是平衡二叉树
https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222
思路:
- 1、根据题意，左右子树高度差不能超过1，即Math.abs(leftHigh-rightHigh) <= 1;
- 2、计算出二叉树左右子树的高度，再计算高度差，即可判断是不是平衡的二叉树；
- 3、再分别判断左右子树是不是平衡的；
代码实现：
public static boolean isBalanceTree(TreeNode root) {
if (root == null)
return true;
int diff = traverse(root.left) - traverse(root.right);
return (Math.abs(diff) <= 1) && isBalanceTree(root.left) && isBalanceTree(root.right);
}
/**
* 后续遍历计算二叉树的高度
*
* @param root
* @return
*/
private static int traverse(TreeNode root) {
if (root == null)
return 0;
int left = traverse(root.left);
int right = traverse(root.right);
return Math.max(left, right) + 1;
}我的刷题题解 文章被收录于专栏
自己在刷题过程中的一些思路和见解记录
木的办法， 以后越来越差，还是家附近宅着吧，毕业的人越来越多，岗位都提供不出来，经济又过了人口红利期
查看30道真题和解析