/**
*
* @author gentleKay
* 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。
*
*/
在解决这道题目之前,我们必须要知道如何求一个二叉树的深度?
public int getDepth(TreeNode root) { if (root == null ) { return 0; } int left = getDepth(root.left)+1; //每迭代一次,深度就+1
int right = getDepth(root.right)+1; return left > right ? left : right ; }
我们再来分析一下题目,自从我们知道了 如何求一个二叉树的深度之后,这道题就比较简单了。
/** * * @author gentleKay * 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。 * */ public class Main19 { public static void main(String[] args) { // TODO Auto-generated method stub TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); // root.right = new TreeNode(3); // root.right.left = new TreeNode(6); // root.right.right = new TreeNode(7); System.out.println(Main19.isBalanced(root)); } public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public static boolean isBalanced(TreeNode root) { if (root == null) { return true; } int left = getDepth(root.left); //拿到 相当于根节点的左右两个节点的深度 int right = getDepth(root.right); if (Math.abs(left-right) > 1) { //并比较不超过 1 ,超过了 返回 false。 return false; } return isBalanced(root.left) && isBalanced(root.right); // 在进行迭代,根节点的左右节点的左右节点进行分析深度与否。 } public static int getDepth(TreeNode root) { if (root == null ) { return 0; } int left = getDepth(root.left)+1; int right = getDepth(root.right)+1; return left > right ? left : right ; } }