确定二叉树是否平衡

Question

我目前正在分析一些编码面试问题，我对4-4的解决方案与任何给定的解决方案都有很大的不同。

这个问题要求确定给定的二叉树是否是平衡的；更具体地说，该树内的最大深度和最小深度之间的差值是否小于或等于1。

public static bool IsBalanced(Node node)
{
    var mm = new DepthMinMax();
    mm.Min = int.MaxValue;
    mm.Max = int.MinValue;

    FindMinMax(mm, node, 0);

    return (mm.Max - mm.Min <= 1) ? true : false;
}

private static void FindMinMax(DepthMinMax mm, Node node, int depth)
{
    if (node == null) return;

    FindMinMax(mm, node.L, depth + 1);
    FindMinMax(mm, node.R, depth + 1);

    // At a terminating node
    if (node.L == null || node.R == null)
    {
        if (mm.Min > depth) mm.Min = depth;
        if (mm.Max < depth) mm.Max = depth;
    }
}

public class Node
{
    public Node L { get; set; }
    public Node R { get; set; }
}

public class DepthMinMax
{
    public int Min { get; set; }
    public int Max { get; set; }
}

这适用于我的测试用例，但它们还远远不够详尽，如果我的解决方案对所有的用例/都是有效的，我不能真正得出结论。我的解决方案感觉太简单了，这让我相信我错过了一些问题。

Answer 1

当我在这本书中回答同样的问题时，偶然发现了这篇文章。在解决这一问题上，我的方法也是类似的。我会张贴我发现的答案，因为我不能评论。

首先，我认为检查终止节点的or条件是不正确的。据我理解，这应该是一个and条件。我认为在更新深度之前，我们需要识别当前节点是否是叶节点。对于下面的树，这将给出最大深度为3，最小深度为1，这是不正确的。我是在C++中这样做的，如下所示。

      5
     /  \
    4    7
   /    / \
  1    6   8 
 /
0  


 void FindMinMax(int &min,int &max,Node *np,int height)
 {
     if(np==NULL) return;
     FindMinMax(min,max,np->left,height+1);
     FindMinMax(min,max,np->right,height+1);

     if(np->left==NULL || np->right==NULL)
     {
         if(min>height) min = height;
         if(max<height) max = height;
     }
 }

第二，我不知道是否有不同的版本。在我的书中，问题4.1是关于检查二叉树是否是平衡的。这被定义为

任何节点的两个子树的高度都不会有一个以上的差异。

如果这是我的要求，我认为这个算法是行不通的。检查这个问题的前两个答案。我认为这个算法检查离根最远的叶子和最近的叶子之间是否有一个以上的差别。

编辑:在这里，我假设最小最大值对应于叶节点的最大深度和最小深度。

Answer 2

一个简短的注释，这句话：

return (mm.Max - mm.Min <= 1) ? true : false;

简化为：

return (mm.Max - mm.Min) <= 1;

因为它已经是一个布尔表达式了。

Answer 3

从面试官的角度来看，这是我最关注的：

• 注释不需要注释注释解释一段代码，它并不是不言自明的。每次你想写评论的时候，都要三思而后行--也许有更好的方式来表达你的意图。//在一个终止节点if (node.L == null / == null)是一个很好的例子。如果您觉得条件不清楚，给它一个好名字，并删除注释: If (node.is_leaf())
• 算法如果左子树不平衡，检查右子树是没有意义的。不解决这一问题的解决办法不是解决办法。