logo标签列表

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

javaalgorithmdata-structuresbinary-tree
117

离开那些校园已经有一段时间了。我在医院找到了一个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;
}

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

如果您想查看Donal Fellows的带有图形的ASCII二叉树，请访问：http://i.imgur.com/97C27Ek.png - user7643681
1
好的回答，帮助我进入美国。（开玩笑） - Henry
28个回答
3

这是一个完整的C#解决方案（抱歉，我不是Java开发人员）（只需在控制台应用程序中复制粘贴即可）。

我知道平衡的定义因人而异，因此并不是每个人都喜欢我的测试结果，但请看一下递归循环中检查深度/高度的略有不同的方法，如果出现第一个不匹配就退出，而不保存每个节点的高度/级别/深度（仅在函数调用中维护它）。

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);
            }
        }
    }
}
我不明白为什么有人在回答发布后的2分钟内就给出了负面评价？负面评价没关系，但您能否解释一下这个解决方案有什么问题吗？ - sbp
3
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));
}
我认为这个解决方案不正确。如果你传递一个只有一个节点即根节点的树，它将返回最大深度为1（最小深度同理）。然而，正确的深度应该是0。一棵树的根节点深度始终为0。 - Cratylus
3
通常，平衡取决于每个方向上最长路径的长度。上述算法不会为您完成这项工作。
您要实现什么？有自平衡树（AVL/红黑树）可用。实际上，Java树已经是平衡的。
2
#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;
}
您可能希望添加一些注释 - jgauffin
2
1
这里提供了一种基于通用深度优先遍历的版本。应该比其他正确答案更快，并且可以处理所有提到的“挑战”。对不起，我不太懂Java，所以风格可能有些奇怪。
如果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 );
}
1
虽然不错的尝试，但它显然不起作用。让 x 成为一个空节点。将非空树节点表示为 (LEFT VALUE RIGHT)。考虑树 (x A (x B x))。 "root" 指向节点 A、B、A、B、A、B......永远循环。要再试一次吗？提示：没有父指针实际上更容易。 - Eric Lippert
@Eric：糟糕，已修复（我想）。好吧，我正在尝试在不使用O(depth)内存的情况下完成此操作，如果结构没有父指针（通常没有），则需要使用堆栈。 - Potatoswatter
@Eric 回复1：如果您已经将父指针用于其他用途，则不是虚假的经济。回复2：当然可以，但这是一种奇怪的调试方式...我不应该在凌晨4点盲目地编写任何遍历操作... - Potatoswatter
此外，验证树的平衡性而不进行平衡的原因是为了让您编写一个测试套件来验证您的树平衡器是否正确！ - Eric Lippert
@Eric：那是我昨晚做出的更改。至于带有O(1)内存（给定父链接）的AVL测试器，只需使用此答案作为O(1)-内存深度优先遍历的模板，并在每个节点执行嵌套的深度优先遍历以查找其子树的高度。这将使用O(1)内存（但O(N)父链接）和O(N^2)时间。 - Potatoswatter
显示剩余9条评论
1

好的，你需要一种方法来确定左右子树的高度，并且判断左右子树是否平衡。

我会直接return height(node->left) == height(node->right);

至于编写一个height函数，请参考： 理解递归

3
您希望左右两侧的高度差不超过1，不一定要完全相等。 - Alex B
1
你在谈论什么样的树呢？有自平衡树存在。请检查它们的算法，以确定是否需要重新排序树来保持平衡。
1
class Node {
    int data;
    Node left;
    Node right;

    // assign variable with constructor
    public Node(int data) {
        this.data = data;
    }
}

public class BinaryTree {

    Node root;

    // get max depth
    public static int maxDepth(Node node) {
        if (node == null)
            return 0;

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

    // get min depth
    public static int minDepth(Node node) {
        if (node == null)
            return 0;

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

    // return max-min<=1 to check if tree balanced
    public boolean isBalanced(Node node) {

        if (Math.abs(maxDepth(node) - minDepth(node)) <= 1)
            return true;

        return false;
    }

    public static void main(String... strings) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);


        if (tree.isBalanced(tree.root))
            System.out.println("Tree is balanced");
        else
            System.out.println("Tree is not balanced");
    }
}
1

关于使用BFS进行层序遍历的@lucky解决方案，我们遍历树并保留对min/max-level变量的引用，这些变量描述了节点作为叶子节点的最小级别。

我认为@lucky的解决方案需要修改。正如@codaddict所建议的那样，我们必须检查左右子节点是否为空（而不是两者都为空）才能判断节点是否为叶子节点。否则，该算法将认为这是一个有效的平衡树：

     1
    / \
   2   4
    \   \
     3   1

在Python中：

def is_bal(root):
    if root is None:
        return True

    import queue

    Q = queue.Queue()
    Q.put(root)

    level = 0
    min_level, max_level = sys.maxsize, sys.minsize

    while not Q.empty():
        level_size = Q.qsize()

        for i in range(level_size):
            node = Q.get()

            if not node.left or node.right:
                min_level, max_level = min(min_level, level), max(max_level, level)

            if node.left:
                Q.put(node.left)
            if node.right:
                Q.put(node.right)

        level += 1

        if abs(max_level - min_level) > 1:
            return False

    return True

这个解决方案应该满足初始问题中提供的所有规定，以O(n)时间和O(n)空间运行。内存溢出将被指向堆而不是爆炸递归调用栈。或者，我们可以最初遍历树以迭代地计算+缓存每个根子树的最大高度。然后在另一个迭代运行中，检查每个根的左右子树的缓存高度是否从未相差超过一。这也将以O(n)时间和O(n)空间运行，但是迭代运行，以免导致堆栈溢出。
看起来你的决定是错误的，请检查树： Node root1 = new Node(1); root1.left = new Node(2); root1.right = new Node(3); root1.left.left = new Node(4); root1.left.right = new Node(5); root1.right.right = new Node(6); root1.left.left.left = new Node(7); root1.left.left.right = new Node(8); - Megaprog
仅适用于少数情况。 我对这组单元测试进行了测试： https://leetcode.com/problems/balanced-binary-tree/ - Davide Pugliese
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接