如何确定二叉树是否平衡?

It's been a while from those school years. Got a job as IT specialist at a hospital. Trying to move to do some actual programming now. I'm working on binary trees now, and I was wondering what would be the best way to determine if the tree is height-balanced.

这段时间已经有一段时间了。在一家医院找到了一份IT专家的工作。现在尝试着去做一些实际的编程。我现在正在研究二叉树，我想知道如果树是高度平衡的最好的方法是什么。

I was thinking of something along this:

我在想一些事情:

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;
}

Is this a good implementation? or am I missing something?

这是一个好的实现吗?还是我漏掉了什么?

25 个解决方案

#1

Stumbled across this old question while searching for something else. I notice that you never did get a complete answer.

在寻找其他东西时，偶然发现了这个老问题。我注意到你从来没有得到一个完整的答案。

The way to solve this problem is to start by writing a specification for the function you are trying to write.

解决这个问题的方法是先为您要编写的函数编写一个规范。

Specification: A well-formed binary tree is said to be "height-balanced" if (1) it is empty, or (2) its left and right children are height-balanced and the height of the left tree is within 1 of the height of the right tree.

说明:一种结构良好的二叉树被认为是“高度平衡”的，如果它是空的，或者(2)它的左和右子是高度平衡的，左边树的高度在右树高度的1以内。

Now that you have the specification, the code is trivial to write. Just follow the specification:

既然已经有了规范，那么编写代码就很简单了。只是遵循该规范:

IsHeightBalanced(tree)
    return (tree is empty) or 
           (IsHeightBalanced(tree.left) and
            IsHeightBalanced(tree.right) and
            abs(Height(tree.left) - Height(tree.right)) <= 1)

Translating that into the programming language of your choice should be trivial.

将其翻译成您所选择的编程语言应该是微不足道的。

Bonus exercise: this naive code sketch traverses the tree far too many times when computing the heights. Can you make it more efficient?

奖励练习:这个简单的代码草图在计算高度时遍历树的次数太多了。你能让它更有效率吗?

Super bonus exercise: suppose the tree is massively unbalanced. Like, a million nodes deep on one side and three deep on the other. Is there a scenario in which this algorithm blows the stack? Can you fix the implementation so that it never blows the stack, even when given a massively unbalanced tree?

超级奖励练习:假设树非常不平衡。比如，一边有100万个节点，另一边有3个深节点。是否有一种情况下，这个算法会使堆栈崩溃?你能修复这个实现吗?这样它就不会吹掉堆栈，即使是在给定一棵巨大的不平衡树的时候?

UPDATE: Donal Fellows points out in his answer that there are different definitions of 'balanced' that one could choose. For example, one could take a stricter definition of "height balanced", and require that the path length to the nearest empty child is within one of the path to the farthest empty child. My definition is less strict than that, and therefore admits more trees.

更新:Donal研究员在他的回答中指出，人们可以选择“平衡”的不同定义。例如，一个人可以对“高度平衡”进行更严格的定义，并且要求距离最近的空孩子的路径长度是在距离最远的空孩子的路径的一条路径之内。我的定义不那么严格，因此允许更多的树。

One can also be less strict than my definition; one could say that a balanced tree is one in which the maximum path length to an empty tree on each branch differs by no more than two, or three, or some other constant. Or that the maximum path length is some fraction of the minimum path length, like a half or a quarter.

你也可以不像我的定义那样严格;可以这样说，平衡树是指每个分支上的空树的最大路径长度不超过2、3或其他常数。或者最大路径长度是最小路径长度的一部分，比如1 / 2或1 / 4。

It really doesn't matter usually. The point of any tree-balancing algorithm is to ensure that you do not wind up in the situation where you have a million nodes on one side and three on the other. Donal's definition is fine in theory, but in practice it is a pain coming up with a tree-balancing algorithm that meets that level of strictness. The performance savings usually does not justify the implementation cost. You spend a lot of time doing unnecessary tree rearrangements in order to attain a level of balance that in practice makes little difference. Who cares if sometimes it takes forty branches to get to the farthest leaf in a million-node imperfectly-balanced tree when it could in theory take only twenty in a perfectly balanced tree? The point is that it doesn't ever take a million. Getting from a worst case of a million down to a worst case of forty is usually good enough; you don't have to go all the way to the optimal case.

通常都无所谓。任何树平衡算法的目的都是为了确保你不会在这样的情况下出现，在这种情况下，一边有100万个节点，另一边有3个节点。Donal的定义在理论上是可以的，但在实践中，它是一种痛苦，它提出了一种树平衡算法，达到了这种程度的严格性。性能节省通常不为实现成本提供理由。为了达到一种平衡的水平，你花了很多时间去做不必要的树木重新安排，这在实践中几乎没有什么差别。谁会在意，有时它需要40根树枝才能到达100万节点不完全平衡的树的最远的叶子呢?理论上，在一棵完全平衡的树上，它只需要20根树枝?关键是它从来没有花过一百万。从100万的最坏情况到最坏的40个情况，通常是足够好的;你不需要一直走到最优情况。

#2

Balance is a truly subtle property; you think you know what it is, but it's so easy to get wrong. In particular, even Eric Lippert's (good) answer is off. That's because the notion of height is not enough. You need to have the concept of minimum and maximum heights of a tree (where the minimum height is the least number of steps from the root to a leaf, and the maximum is... well, you get the picture). Given that, we can define balance to be:

平衡是一种真正微妙的特性;你以为你知道它是什么，但它很容易出错。特别是Eric Lippert的(好)答案是off，这是因为高度的概念是不够的。您需要有树的最小和最大高度的概念(最低高度是从根到叶的最小步数，最大值是…)你懂的。考虑到这一点，我们可以把平衡定义为:

A tree where the maximum height of any branch is no more than one more than the minimum height of any branch.

任何分支的最大高度不超过任何分支的最小高度的树。

(This actually implies that the branches are themselves balanced; you can pick the same branch for both maximum and minimum.)

(这实际上意味着分支本身是平衡的;您可以选择相同的分支，以达到最大值和最小值。

All you need to do to verify this property is a simple tree traversal keeping track of the current depth. The first time you backtrack, that gives you a baseline depth. Each time after that when you backtrack, you compare the new depth against the baseline

要验证这个属性，您需要做的只是一个简单的树遍历跟踪当前的深度。第一次回溯的时候，会给你一个基线深度。每次当你回溯的时候，你会比较新的深度和基线。

• if it's equal to the baseline, then you just continue
• 如果它等于基线，那么你就继续。
• if it is more than one different, the tree isn't balanced
• 如果它不止一个，树就不平衡了。
• if it is one off, then you now know the range for balance, and all subsequent depths (when you're about to backtrack) must be either the first or the second value.
• 如果它是一个off，那么您现在知道了平衡的范围，并且所有后续的深度(当您要回溯的时候)必须要么是第一个值，要么是第二个值。

In code:

在代码:

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;
            }
        });
    }
}

I suppose you could do this without using the Observer pattern, but I find it easier to reason this way.

我想你可以不使用观察者模式来做这个，但是我发现这样做更容易。

---

[EDIT]: Why you can't just take the height of each side. Consider this tree:

[编辑]:为什么你不能只取每一边的高度。考虑这棵树:

        /\
       /  \
      /    \
     /      \_____
    /\      /     \_
   /  \    /      / \
  /\   C  /\     /   \
 /  \    /  \   /\   /\
A    B  D    E F  G H  J

OK, a bit messy, but each side of the root is balanced: C is depth 2, A, B, D, E are depth 3, and F, G, H, J are depth 4. The height of the left branch is 2 (remember the height decreases as you traverse the branch), the height of the right branch is 3. Yet the overall tree is not balanced as there is a difference in height of 2 between C and F. You need a minimax specification (though the actual algorithm can be less complex as there should be only two permitted heights).

好，有点乱，但是根的两边是平衡的:C是深度2,a, B, D, E是深度3,F, G, H, J是深度4。左分支的高度为2(记住，当你遍历分支时，高度减小)，右分支的高度为3。但是，总体树不平衡，因为C和f之间的高度差是2。你需要一个极小的规范(尽管实际的算法可能不那么复杂，因为应该只有两个允许的高度)。

#3

Bonus exercise response. The simple solution. Obviously in a real implementation one might wrap this or something to avoid requiring the user to include height in their response.

奖金运动响应。简单的解决方案。很明显，在真正的实现中，可能会把这个或一些东西包装起来，以避免要求用户在响应中包含高度。

IsHeightBalanced(tree, out height)
    if (tree is empty)
        height = 0
        return true
    balance = IsHeightBalanced(tree.left, heightleft) and IsHeightBalanced(tree.right, heightright)
    height = max(heightleft, heightright)+1
    return balance and abs(heightleft - heightright) <= 1     

#4

This only determines if the top level of the tree is balanced. That is, you could have a tree with two long branches off the far left and far right, with nothing in the middle, and this would return true. You need to recursively check the root.left and root.right to see if they are internally balanced as well before returning true.

这只决定了树的顶层是否平衡。也就是说，你可以有一棵树，它有两根长树枝，在最左边和最右边，中间没有任何东西，这就会返回真值。您需要递归地检查根。和根。在返回真值之前，看看它们是否在内部平衡。

#5

Post order solution, traverse the tree only once. Time complexity is O(n), space is O(1), it's better than top-down solution. I give you a java version implementation.

邮购解决方案，只遍历树一次。时间复杂度是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);
    }
}

#6

The definition of a height-balanced binary tree is:

高度平衡二叉树的定义是:

Binary tree in which the height of the two subtrees of every node never differ by more than 1.

二叉树，其中每个结点的两个子树的高度从不相差超过1。

So, An empty binary tree is always height-balanced.
A non-empty binary tree is height-balanced if:

所以，一个空的二叉树总是高度平衡的。非空二叉树的高度平衡:

1. Its left subtree is height-balanced.
2. 它的左子树高度平衡。
3. Its right subtree is height-balanced.
4. 它的右子树高度平衡。
5. The difference between heights of left & right subtree is not greater than 1.
6. 左和右子树的高度差不大于1。

Consider the tree:

考虑树:

    A
     \ 
      B
     / \
    C   D

As seen the left subtree of A is height-balanced (as it is empty) and so is its right subtree. But still the tree is not height-balanced as condition 3 is not met as height of left-subtree is 0 and height of right sub-tree is 2.

当看到A的左子树是高度平衡的(因为它是空的)，它的右子树也是如此。但树不是高度平衡的，条件3不满足，左子树高度为0，右子树高度为2。

Also the following tree is not height balanced even though the height of left and right sub-tree are equal. Your existing code will return true for it.

另外，虽然左和右子树的高度相等，下面的树也不是高度平衡的。您现有的代码将返回true。

       A
     /  \ 
    B    C
   /      \
  D        G
 /          \
E            H

So the word every in the def is very important.

所以def中的每个词都很重要。

This will work:

这将工作:

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);
}

Ideone Link

Ideone链接

#7

This is being made way more complicated than it actually is.

这比实际情况要复杂得多。

The algorithm is as follows:

该算法如下:

1. Let A = depth of the highest-level node
2. 让A = depth的*节点。

3. Let B = depth of the lowest-level node

   让B =最低层节点的深度。

4. If abs(A-B) <= 1, then the tree is balanced

   如果ab (A-B) <= 1，那么树是平衡的。

#8

What balanced means depends a bit on the structure at hand. For instance, A B-Tree cannot have nodes more than a certain depth from the root, or less for that matter, all data lives at a fixed depth from the root, but it can be out of balance if the distribution of leaves to leaves-but-one nodes is uneven. Skip-lists Have no notion at all of balance, relying instead on probability to achieve decent performance. Fibonacci trees purposefully fall out of balance, postponing the rebalance to achieve superior asymptotic performance in exchange for occasionally longer updates. AVL and Red-Black trees attach metadata to each node to attain a depth-balance invariant.

平衡的方式取决于手头的结构。例如，b树不能有超过一定深度的节点，或者更少，所有的数据都是从根结点处固定的深度，但是如果叶节点的分布不均匀，那么它就会失去平衡。在所有的平衡中，skiplist都没有概念，而是依靠概率来获得良好的性能。斐波那契树有目的地失去平衡，推迟再平衡，以获得更好的渐近性能，以换取偶尔的更新。AVL和红黑树将元数据附加到每个节点上，以达到深度平衡不变。

All of these structures and more are present in the standard libraries of most common programming systems (except python, RAGE!). Implementing one or two is good programming practice, but its probably not a good use of time to roll your own for production, unless your problem has some peculiar performance need not satisfied by any off-the-shelf collections.

所有这些结构和更多的东西都存在于最常见的编程系统的标准库中(除了python, RAGE!)实现一个或两个是良好的编程实践，但它可能不是很好地利用时间来进行生产，除非您的问题有一些特殊的性能，不需要任何现成的集合来满足。

#9

Note 1: The height of any sub-tree is computed only once.

注1:任何子树的高度只计算一次。

Note 2: If the left sub-tree is unbalanced then the computation of the right sub-tree, potentially containing million elements, is skipped.

注2:如果左子树不平衡，则跳过右子树的计算，可能包含上百万个元素。

// 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;
}

#10

If binary tree is balanced or not can be checked by Level order traversal:

如果二叉树是平衡的，或者不能通过水平顺序遍历来检查:

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;
}

#11

Balancing usually depends on the length of the longest path on each direction. The above algorithm is not going to do that for you.

平衡通常取决于每个方向上最长路径的长度。上面的算法不会为你做这些。

What are you trying to implement? There are self-balancing trees around (AVL/Red-black). In fact, Java trees are balanced.

你想要实现什么?周围有自动平衡树(AVL/Red-black)。事实上，Java树是平衡的。

#12

If this is for your job, I suggest:

如果这是你的工作，我建议:

1. do not reinvent the wheel and
2. 不要重新发明*和?
3. use/buy COTS instead of fiddling with bits.
4. 用/买COTS，而不是用小块。
5. Save your time/energy for solving business problems.
6. 节省时间/精力来解决商业问题。

#13

public boolean isBalanced(TreeNode root)
{
    return (maxDepth(root) - minDepth(root) <= 1);
}

public int maxDepth(TreeNode root)
{
    if (root == null) return 0;

    return 1 + max(maxDepth(root.left), maxDepth(root.right));
}

public int minDepth (TreeNode root)
{
    if (root == null) return 0;

    return 1 + min(minDepth(root.left), minDepth(root.right));
}

#14

#include <iostream>
#include <deque>
#include <queue>

struct node
{
    int data;
    node *left;
    node *right;
};

bool isBalanced(node *root)
{
    if ( !root)
    {
        return true;
    }

    std::queue<node *> q1;
    std::queue<int>  q2;
    int level = 0, last_level = -1, node_count = 0;

    q1.push(root);
    q2.push(level);

    while ( !q1.empty() )
    {
        node *current = q1.front();
        level = q2.front();

        q1.pop();
        q2.pop();

        if ( level )
        {
            ++node_count;
        }

                if ( current->left )
                {
                        q1.push(current->left);
                        q2.push(level + 1);
                }

                if ( current->right )
                {
                        q1.push(current->right);
                        q2.push(level + 1);
                }

        if ( level != last_level )
        {
            std::cout << "Check: " << (node_count ? node_count - 1 : 1) << ", Level: " << level << ", Old level: " << last_level << std::endl;
            if ( level && (node_count - 1) != (1 << (level-1)) )
            {
                return false;
            }

            last_level = q2.front();
            if ( level ) node_count = 1;
        }
    }

    return true;
}

int main()
{
    node tree[15];

    tree[0].left  = &tree[1];
    tree[0].right = &tree[2];
    tree[1].left  = &tree[3];
    tree[1].right = &tree[4];
    tree[2].left  = &tree[5];
    tree[2].right = &tree[6];
    tree[3].left  = &tree[7];
    tree[3].right = &tree[8];
    tree[4].left  = &tree[9];   // NULL;
    tree[4].right = &tree[10];  // NULL;
    tree[5].left  = &tree[11];  // NULL;
    tree[5].right = &tree[12];  // NULL;
    tree[6].left  = &tree[13];
    tree[6].right = &tree[14];
    tree[7].left  = &tree[11];
    tree[7].right = &tree[12];
    tree[8].left  = NULL;
    tree[8].right = &tree[10];
    tree[9].left  = NULL;
    tree[9].right = &tree[10];
    tree[10].left = NULL;
    tree[10].right= NULL;
    tree[11].left = NULL;
    tree[11].right= NULL;
    tree[12].left = NULL;
    tree[12].right= NULL;
    tree[13].left = NULL;
    tree[13].right= NULL;
    tree[14].left = NULL;
    tree[14].right= NULL;

    std::cout << "Result: " << isBalanced(tree) << std::endl;

    return 0;
}

#15

Here is a complete worked out tested solution in C# (sorry I'm no java dev) (just copy paste in console app). I know that definition of balanced varies so not everyone may like my test results but please just look at the slightly different approach of checking depth/height in a recursive loop and exiting on the first mismatch without saving node height/level/depth on each node (only maintaining it in a function call).

这是一个完整的经过测试的c#测试解决方案(对不起，我不是java dev)(只是在控制台应用程序中复制粘贴)。我知道平衡的定义不同,因此并不是每个人都能喜欢我的测试结果,但请看看稍微不同的方法检查/高深度的递归循环和退出不保存第一个不匹配节点在每个节点上高度/等级/深度(只有维持它在函数调用)。

using System;
using System.Linq;
using System.Text;

namespace BalancedTree
{
    class Program
    {
        public static void Main()
        {
            //Value Gathering
            Console.WriteLine(RunTreeTests(new[] { 0 }));
            Console.WriteLine(RunTreeTests(new int[] { }));

            Console.WriteLine(RunTreeTests(new[] { 0, 1, 2, 3, 4, -1, -4, -3, -2 }));
            Console.WriteLine(RunTreeTests(null));
            Console.WriteLine(RunTreeTests(new[] { 10, 8, 12, 8, 4, 14, 8, 10 }));
            Console.WriteLine(RunTreeTests(new int[] { 20, 10, 30, 5, 15, 25, 35, 3, 8, 12, 17, 22, 27, 32, 37 }));

            Console.ReadKey();
        }

        static string RunTreeTests(int[] scores)
        {
            if (scores == null || scores.Count() == 0)
            {
                return null;
            }

            var tree = new BinarySearchTree();

            foreach (var score in scores)
            {
                tree.InsertScore(score);
            }

            Console.WriteLine(tree.IsBalanced());

            var sb = tree.GetBreadthWardsTraversedNodes();

            return sb.ToString(0, sb.Length - 1);
        }
    }

    public class Node
    {
        public int Value { get; set; }
        public int Count { get; set; }
        public Node RightChild { get; set; }
        public Node LeftChild { get; set; }
        public Node(int value)
        {
            Value = value;
            Count = 1;
        }

        public override string ToString()
        {
            return Value + ":" + Count;
        }

        public bool IsLeafNode()
        {
            return LeftChild == null && RightChild == null;
        }

        public void AddValue(int value)
        {
            if (value == Value)
            {
                Count++;
            }
            else
            {
                if (value > Value)
                {
                    if (RightChild == null)
                    {
                        RightChild = new Node(value);
                    }
                    else
                    {
                        RightChild.AddValue(value);
                    }
                }
                else
                {
                    if (LeftChild == null)
                    {
                        LeftChild = new Node(value);
                    }
                    else
                    {
                        LeftChild.AddValue(value);
                    }
                }
            }
        }
    }

    public class BinarySearchTree
    {
        public Node Root { get; set; }

        public void InsertScore(int score)
        {
            if (Root == null)
            {
                Root = new Node(score);
            }
            else
            {
                Root.AddValue(score);
            }
        }

        private static int _heightCheck;
        public bool IsBalanced()
        {
            _heightCheck = 0;
            var height = 0;
            if (Root == null) return true;
            var result = CheckHeight(Root, ref height);
            height--;
            return (result && height == 0);
        }

        private static bool CheckHeight(Node node, ref int height)
        {
            height++;
            if (node.LeftChild == null)
            {
                if (node.RightChild != null) return false;
                if (_heightCheck != 0) return _heightCheck == height;
                _heightCheck = height;
                return true;
            }
            if (node.RightChild == null)
            {
                return false;
            }

            var leftCheck = CheckHeight(node.LeftChild, ref height);
            if (!leftCheck) return false;
            height--;
            var rightCheck = CheckHeight(node.RightChild, ref height);
            if (!rightCheck) return false;
            height--;
            return true;
        }


        public StringBuilder GetBreadthWardsTraversedNodes()
        {
            if (Root == null) return null;
            var traversQueue = new StringBuilder();
            traversQueue.Append(Root + ",");
            if (Root.IsLeafNode()) return traversQueue;
            TraversBreadthWards(traversQueue, Root);
            return traversQueue;
        }

        private static void TraversBreadthWards(StringBuilder sb, Node node)
        {
            if (node == null) return;
            sb.Append(node.LeftChild + ",");
            sb.Append(node.RightChild + ",");
            if (node.LeftChild != null && !node.LeftChild.IsLeafNode())
            {
                TraversBreadthWards(sb, node.LeftChild);
            }
            if (node.RightChild != null && !node.RightChild.IsLeafNode())
            {
                TraversBreadthWards(sb, node.RightChild);
            }
        }
    }
}

#16

Well, you need a way to determine the heights of left and right, and if left and right are balanced.

你需要一种方法来确定左右两边的高度，如果左边和右边是平衡的。

And I'd just return height(node->left) == height(node->right);

然后返回高度(节点->左侧)== height(节点->右侧);

As to writing a height function, read: Understanding recursion

至于写高度函数，请阅读:理解递归。

#17

What kind of tree are you talking about? There are self-balancing trees out there. Check their algorithms where they determine if they need to reorder the tree in order to maintain balance.

你说的是哪种树?那里有自我平衡的树木。检查他们的算法，确定他们是否需要重新排序树以保持平衡。

#18

Here is a version based on a generic depth-first traversal. Should be faster than the other correct answer and handle all the mentioned "challenges." Apologies for the style, I don't really know Java.

这是一个基于通用深度优先遍历的版本。应该比另一个正确的答案快，并且处理所有提到的“挑战”。抱歉，我不太懂Java。

You can still make it much faster by returning early if max and min are both set and have a difference >1.

如果max和min都设置好了，并且有不同的>1，那么您仍然可以更快地返回。

public boolean isBalanced( Node root ) {
    int curDepth = 0, maxLeaf = 0, minLeaf = INT_MAX;
    if ( root == null ) return true;
    while ( root != null ) {
        if ( root.left == null || root.right == null ) {
            maxLeaf = max( maxLeaf, curDepth );
            minLeaf = min( minLeaf, curDepth );
        }
        if ( root.left != null ) {
            curDepth += 1;
            root = root.left;
        } else {
            Node last = root;
            while ( root != null
             && ( root.right == null || root.right == last ) ) {
                curDepth -= 1;
                last = root;
                root = root.parent;
            }
            if ( root != null ) {
                curDepth += 1;
                root = root.right;
            }
        }
    }
    return ( maxLeaf - minLeaf <= 1 );
}

#19

boolean isBalanced(Node root) {
    if (longestPath(root) - shortestPath(root) > 1)
        return false;
    else
        return true;
}


int longestPath(Node root) {
    if (root == null);
        return 0;
    else {
        int leftPathLength = longestPath(root.left);
        int rightPathLength = longestPath(root.right);
        if (leftPathLength >= rightPathLength)
            return leftPathLength + 1;
        else
            return rightPathLength + 1;
    }
}

int shortestPath(Node root) {
    if (root == null);
        return 0;
    else {
        int leftPathLength = shortestPath(root.left);
        int rightPathLength = shortestPath(root.right);
        if (leftPathLength <= rightPathLength)
            return leftPathLength + 1;
        else
            return rightPathLength + 1;
    }
}

#20

Here's what i have tried for Eric's bonus exercise. I try to unwind of my recursive loops and return as soon as I find a subtree to be not balanced.

这是我为埃里克的奖金运动所做的努力。当我发现子树不平衡时，我试着解回递归循环并返回。

int heightBalanced(node *root){
    int i = 1;
    heightBalancedRecursive(root, &i);
    return i; 
} 

int heightBalancedRecursive(node *root, int *i){

    int lb = 0, rb = 0;

    if(!root || ! *i)  // if node is null or a subtree is not height balanced
           return 0;  

    lb = heightBalancedRecursive(root -> left,i);

    if (!*i)         // subtree is not balanced. Skip traversing the tree anymore
        return 0;

    rb = heightBalancedRecursive(root -> right,i)

    if (abs(lb - rb) > 1)  // not balanced. Make i zero.
        *i = 0;

    return ( lb > rb ? lb +1 : rb + 1); // return the current height of the subtree
}

#21

public int height(Node node){
    if(node==null)return 0;
    else{
        int l=height(node.leftChild);
        int r=height(node.rightChild);
       return(l>r?l+1:r+1);

}}
public boolean balanced(Node n){

    int l= height(n.leftChild);
    int r= height(n.rightChild);

    System.out.println(l + " " +r);
    if(Math.abs(l-r)>1)
        return false;
    else 
        return true;
    }

#22

An empty tree is height-balanced. A non-empty binary tree T is balanced if:

空的树是高度平衡的。一个非空的二叉树T是平衡的:

1) Left subtree of T is balanced

1)T的左子树是平衡的。

2) Right subtree of T is balanced

2)T的右子树是平衡的。

3) The difference between heights of left subtree and right subtree is not more than 1.

3)左子树高度与右子树高度差不大于1。

/* program to check if a tree is height-balanced or not */
#include<stdio.h>
#include<stdlib.h>
#define bool int

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
  int data;
  struct node* left;
  struct node* right;
};

/* The function returns true if root is balanced else false
   The second parameter is to store the height of tree.  
   Initially, we need to pass a pointer to a location with value 
   as 0. We can also write a wrapper over this function */
bool isBalanced(struct node *root, int* height)
{
  /* lh --> Height of left subtree 
     rh --> Height of right subtree */   
  int lh = 0, rh = 0;  

  /* l will be true if left subtree is balanced 
    and r will be true if right subtree is balanced */
  int l = 0, r = 0;

  if(root == NULL)
  {
    *height = 0;
     return 1;
  }

  /* Get the heights of left and right subtrees in lh and rh 
    And store the returned values in l and r */   
  l = isBalanced(root->left, &lh);
  r = isBalanced(root->right,&rh);

  /* Height of current node is max of heights of left and 
     right subtrees plus 1*/   
  *height = (lh > rh? lh: rh) + 1;

  /* If difference between heights of left and right 
     subtrees is more than 2 then this node is not balanced
     so return 0 */
  if((lh - rh >= 2) || (rh - lh >= 2))
    return 0;

  /* If this node is balanced and left and right subtrees 
    are balanced then return true */
  else return l&&r;
}


/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */

/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
    struct node* node = (struct node*)
                                malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return(node);
}

int main()
{
  int height = 0;

  /* Constructed binary tree is
             1
           /   \
         2      3
       /  \    /
     4     5  6
    /
   7
  */   
  struct node *root = newNode(1);  
  root->left = newNode(2);
  root->right = newNode(3);
  root->left->left = newNode(4);
  root->left->right = newNode(5);
  root->right->left = newNode(6);
  root->left->left->left = newNode(7);

  if(isBalanced(root, &height))
    printf("Tree is balanced");
  else
    printf("Tree is not balanced");    

  getchar();
  return 0;
}

Time Complexity: O(n)

时间复杂度:O(n)

#23

To have a better performance specially on huge trees you can save the height in each node so it is a trade off space Vs performance:

为了在巨大的树上有更好的性能，你可以在每个节点上节省高度，所以这是一种空间与性能的权衡:

class Node {
    Node left;
    Node right;
    int value;
    int height;
}

Example of implementing the addition and same for deletion

示例实现添加和删除相同。

void addNode(Node root,int v)
{    int height =0;
     while(root != null)
     {
         // Since we are adding new node so the height 
         // will increase by one in each node we will pass by
         root.height += 1;
         height++;
         else if(v > root.value){
            root = root.left();
            }
         else{
         root = root.right();
         }

     }

         height++;
         Node n = new Node(v , height);
         root = n;         
}
int treeMaxHeight(Node root)
{
 return Math.Max(root.left.height,root.right.height);
}

int treeMinHeight(Node root)
{
 return Math.Min(root.left.height,root.right.height);

}

Boolean isNodeBlanced(Node root)
{
   if (treeMaxHeight(root) - treeMinHeight(root) > 2)
       return false;

  return true;
}

Boolean isTreeBlanced (Node root)
{
    if(root == null || isTreeBalanced(root.left) && isTreeBalanced(root.right) && isNodeBlanced(root))
    return true;

  return false;

}

#24

    static boolean isBalanced(Node root) {
    //check in the depth of left and right subtree
    int diff = depth(root.getLeft()) - depth(root.getRight());
    if (diff < 0) {
        diff = diff * -1;
    }
    if (diff > 1) {
        return false;
    }
    //go to child nodes
    else {
        if (root.getLeft() == null && root.getRight() == null) {
            return true;
        } else if (root.getLeft() == null) {
            if (depth(root.getRight()) > 1) {
                return false;
            } else {
                return true;
            }
        } else if (root.getRight() == null) {
            if (depth(root.getLeft()) > 1) {
                return false;
            } else {
                return true;
            }
        } else if (root.getLeft() != null && root.getRight() != null && isBalanced(root.getLeft()) && isBalanced(root.getRight())) {
            return true;
        } else {
            return false;
        }
    }
}

#25

Wouldn't this work?

不是这个工作?

return ( ( Math.abs( size( root.left ) - size( root.right ) ) < 2 );

Any unbalanced tree would always fail this.

任何不平衡的树都会失败。