Balanced Binary Tree
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就返回false,如果小于1,递归判断左右子树是否为平衡树。代码如下:
/**
* Definition for a binary tree node.
* 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 = getDepth(root.left, 1);
int right = getDepth(root.right, 1);
if(left - right > 1 || left - right < -1) {
return false;
} else {
return isBalanced(root.left) && isBalanced(root.right);
}
}
public int getDepth(TreeNode root, int depth) {
if(root == null) return depth;
return Math.max(getDepth(root.left, depth + 1), getDepth(root.right, depth + 1));
}
}