平衡二叉树解决方案

Question

我在 LeetCode 中解决了一个关于二叉平衡树的问题，它非常基本。我对解决方案有疑问，这就是我到目前为止所做的 - 平衡二叉树。我的尝试如下，幸运的是它被接受了：

static bool IsBalanced(BinaryTree root) {
    isBalanced = true;

    int chk = CheckBalance(root.Root, 0);

    return isBalanced;
  }

  static int CheckBalance(TreeNode root, int depth) {
    if (root == null)
      return 0;

    int left = CheckBalance(root.left, depth + 1);
    int right = CheckBalance(root.right, depth + 1);

    if (Math.Abs(left - right) > 1)
      isBalanced = false;
    return GetMax(left, right);
  }

  static int GetMax(int left, int right) {
    if (left > right)
      return left;
    else
      return right;
  }

第一个输入：

       3
      / \
     9  20
        / \
       15  7

输出：真

第二个输入：

        1
       / \
      2   2
     / \
    3   3
   / \
  4   4

输出：假

对于第一个输入，树是平衡的并且返回 true。但对于第二个，它应该返回 false，因为它不平衡。但是当我在小提琴中输入示例时，返回 true。当我对所有可能的树进行递归调用时，是否存在某种错误或错误？

Answer 1

首先是这个：

在

CheckBalance

中，你从不使用

depth

。既然你说它在挑战网站上有效，我必须假设你重新输入了代码并且没有在此处输入相同的代码。基本情况的返回语句应该是：

return depth;

主要问题是您的

Add

函数创建值为

null

的节点实例。这意味着对于第二个示例输入，您实际上创建了这棵树：

            ___1___
           /       \
        __2__       2
       /     \     / \
      3       3 null null
     / \     / \
    4   4 null null

...那棵树是平衡的！

编写一个可以按预期完成工作的

Add

函数并非易事，而无需跟踪

null

子级是否为默认值，或者是否确实由

null

填充。这个差异决定了下一个值应该插入的位置。

因此我建议采用不同的方法。提供一个

BinaryTree

构造函数，它以数组形式接收整个输入，然后以受控方式迭代该数组，将值插入到它们应该结束的位置：

  public BinaryTree(int?[] data) {
    if (data.Length == 0) return;
    
    var queue = new Queue<TreeNode>();
    Root = new TreeNode(data[0]);
    queue.Enqueue(Root);
    
    for (int i = 1; i < data.Length; i++) {
      TreeNode presentNode = queue.Dequeue();
      if (data[i] != null) {
        presentNode.left = new TreeNode(data[i]);
        queue.Enqueue(presentNode.left);
      }
      i++;
      if (i >= data.Length) break;
      if (data[i] != null) {
        presentNode.right = new TreeNode(data[i]);
        queue.Enqueue(presentNode.right);
      }
    }
  }

使用此构造函数，您现在可以像这样运行测试用例：

    int?[] data = {1, 2, 2, 3, 3, null, null, 4, 4};  
    BinaryTree aBinaryTree = new BinaryTree(data);
    bool status = IsBalanced(aBinaryTree);