离开那些校园已经有一段时间了。我在医院找到了一个IT专家的工作。现在正试图转为做一些实际的编程。我现在正在处理二叉树，我想知道确定树是否平衡的最佳方法是什么。
我考虑的方案如下：
public boolean isBalanced(Node root){
if(root==null){
return true; //tree is empty
}
else{
int lh = root.left.height();
int rh = root.right.height();
if(lh - rh > 1 || rh - lh > 1){
return false;
}
}
return true;
}
这是一个好的实现方法吗？还是我漏掉了什么？
在寻找其他东西时偶然发现了这个旧问题。我注意到你从未得到一个完整的答案。
解决这个问题的方法是先为你想要编写的函数编写规范。
规范：如果一个二叉树是"高度平衡的"，那么它必须满足以下条件：(1) 空树，或者(2) 左右子树都是"高度平衡的"并且左子树的高度与右子树之差不超过1。
现在你有了规范，编写代码就很容易了。只需按照规范编写即可：
IsHeightBalanced(tree)
return (tree is empty) or
(IsHeightBalanced(tree.left) and
IsHeightBalanced(tree.right) and
abs(Height(tree.left) - Height(tree.right)) <= 1)
任何分支的最大高度不超过任何分支的最小高度一。
（这实际上意味着分支本身也是平衡的；你可以选择相同的分支作为最大和最小值。）
您只需要执行一个简单的树遍历来验证此属性，并跟踪当前深度。第一次回溯时，这会给您一个基准深度。之后每次回溯时，您将新深度与基准深度进行比较：
代码如下：
class Tree {
Tree left, right;
static interface Observer {
public void before();
public void after();
public boolean end();
}
static boolean traverse(Tree t, Observer o) {
if (t == null) {
return o.end();
} else {
o.before();
try {
if (traverse(left, o))
return traverse(right, o);
return false;
} finally {
o.after();
}
}
}
boolean balanced() {
final Integer[] heights = new Integer[2];
return traverse(this, new Observer() {
int h;
public void before() { h++; }
public void after() { h--; }
public boolean end() {
if (heights[0] == null) {
heights[0] = h;
} else if (Math.abs(heights[0] - h) > 1) {
return false;
} else if (heights[0] != h) {
if (heights[1] == null) {
heights[1] = h;
} else if (heights[1] != h) {
return false;
}
}
return true;
}
});
}
}
我想你可以不使用观察者模式来完成这个任务，但是我发现使用观察者模式更容易理解。
[编辑]: 为什么不能只考虑每一侧的高度呢？考虑下面这棵树：
/\
/ \
/ \
/ \_____
/\ / \_
/ \ / / \
/\ C /\ / \
/ \ / \ /\ /\
A B D E F G H J
好的，有点混乱，但根的两侧是平衡的: C 的深度为2, A, B, D, E 的深度为3，F, G, H, J 的深度为4。左侧分支的高度为2 (记住，随着遍历分支，高度会减少)，右侧分支的高度为3。然而，整个树并不平衡，因为 C 和 F 之间的高度差为2。您需要一个极小值-极大值规范(虽然实际算法可以更简单，因为只应该允许两个高度)。
这只是确定树的顶层是否平衡。也就是说，你可以有一个树，在远左和远右分别有两个长分支，中间什么都没有，但这将返回true。在返回true之前，您需要递归检查root.left和root.right以查看它们是否内部平衡。
额外练习响应。简单的解决方案。显然，在实际实现中，人们可能会将其包装起来或采取其他措施，以避免要求用户在其响应中包含高度。
IsHeightBalanced(tree, out height)
if (tree is empty)
height = 0
return true
balance = IsHeightBalanced(tree.left, out heightleft) and IsHeightBalanced(tree.right, out heightright)
height = max(heightleft, heightright)+1
return balance and abs(heightleft - heightright) <= 1
out height”变量符号） - kapheightleft 和 heightright 是从哪里来的。 - Jac FrallIsHeightBalanced 的第二个参数是一个 out 参数。例如，IsHeightBalanced(tree.left, heightleft) 并没有传递 heightleft 的值，而是计算了 heightleft。我已经编辑了我的答案，使这种使用 out 参数更加明确。 - Brian后序遍历解法，仅遍历一次树。时间复杂度为O(n)，空间复杂度为O(1)，比自顶向下的解法更好。我给你提供一个Java版本的实现。
public static <T> boolean isBalanced(TreeNode<T> root){
return checkBalance(root) != -1;
}
private static <T> int checkBalance(TreeNode<T> node){
if(node == null) return 0;
int left = checkBalance(node.getLeft());
if(left == -1) return -1;
int right = checkBalance(node.getRight());
if(right == -1) return -1;
if(Math.abs(left - right) > 1){
return -1;
}else{
return 1 + Math.max(left, right);
}
}
left == -1 是什么意思？在什么情况下会出现这种情况？我们是否可以假设递归调用意味着如果左子树的所有子树都不平衡，则 left == -1 为真？ - Adrienneleft == 1 表示左子树不平衡，那么整棵树就不平衡了。我们无需再检查右子树，可以直接返回 -1。 - tning平衡二叉树的定义如下：
对于每个节点，其两棵子树的高度差不超过1。
因此，空二叉树一定是平衡的。
对于非空二叉树，当且仅当：
考虑以下树：
A
\
B
/ \
C D
A树不满足第三个条件，即左子树的高度为0，右子树的高度为2，因此它并不是高度平衡的。 A
/ \
B C
/ \
D G
/ \
E H
因此，定义中的every一词非常重要。
这将起作用：
int height(treeNodePtr root) {
return (!root) ? 0: 1 + MAX(height(root->left),height(root->right));
}
bool isHeightBalanced(treeNodePtr root) {
return (root == NULL) ||
(isHeightBalanced(root->left) &&
isHeightBalanced(root->right) &&
abs(height(root->left) - height(root->right)) <=1);
}
可以通过层序遍历来检查二叉树是否平衡：
private boolean isLeaf(TreeNode root) {
if (root.left == null && root.right == null)
return true;
return false;
}
private boolean isBalanced(TreeNode root) {
if (root == null)
return true;
Vector<TreeNode> queue = new Vector<TreeNode>();
int level = 1, minLevel = Integer.MAX_VALUE, maxLevel = Integer.MIN_VALUE;
queue.add(root);
while (!queue.isEmpty()) {
int elementCount = queue.size();
while (elementCount > 0) {
TreeNode node = queue.remove(0);
if (isLeaf(node)) {
if (minLevel > level)
minLevel = level;
if (maxLevel < level)
maxLevel = level;
} else {
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
elementCount--;
}
if (abs(maxLevel - minLevel) > 1) {
return false;
}
level++;
}
return true;
}
这个算法比实际情况复杂得多。
算法如下：
令B = 最低级节点的深度
如果abs(A-B) <= 1，则树是平衡的
// return height of tree rooted at "tn" if, and only if, it is a balanced subtree
// else return -1
int maxHeight( TreeNode const * tn ) {
if( tn ) {
int const lh = maxHeight( tn->left );
if( lh == -1 ) return -1;
int const rh = maxHeight( tn->right );
if( rh == -1 ) return -1;
if( abs( lh - rh ) > 1 ) return -1;
return 1 + max( lh, rh );
}
return 0;
}
bool isBalanced( TreeNode const * root ) {
// Unless the maxHeight is -1, the subtree under "root" is balanced
return maxHeight( root ) != -1;
}