Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
1.解题思路:
首先,二叉平衡树是对于每一个节点来说,其左子树和右字数的高度相差不超过1.则,我们需要定义方法isBanlanced中分别得到左子树和右子树的高度。
如果差小于1,则调用自己,进行该节点左节点和该节点右节点的高度差的判断。如果当前节点为空, 返回true;
其次,在以上过程中,需要定义获得当前节点高度的方法getHight,并且需要递归调用当前节点左节点和右节点getHight从而获得两边的高度,并且返回最高的那个高度+1(1为加入当前节点的高度)。如果当前节点为空,返回0;
AC代码:
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isBalanced(TreeNode root) { if(root==null) return true; int left = getHight(root.left); int right = getHight(root.right); if(Math.abs(left-right)>1) return false; else return isBalanced(root.left) && isBalanced(root.right); } public int getHight(TreeNode root){ if(root==null) return 0; int left = 1+getHight(root.left); int right = 1+getHight(root.right); return left>right?left:right; } }