java - 确定已满的最高级别 - 二叉搜索树

Question

我有一个项目在做，我已经完成了所有的事情，除了我需要找到最高级别的地方，其中有最多的节点。这是我的代码，但我似乎无法弄清楚如何执行此操作:

 public int fullLevel() {
    int height = 1;
    int count = 1;
    fullLevel(root, height, count);
    return height;
} 

private int fullLevel(Node temp, int height, int count) {
    int height2 = (int) Math.pow(2, height - 1);

    if (temp == null) {
        return 0;
    }
    if (count == height2 && temp.left != null && temp.right != null) {
        count = 0;
        return fullLevel(temp.right, count, height + 1) + fullLevel(temp.left, count, height + 1);
    } else if (count != height2) {
        return fullLevel(temp.right, count + 1, height) + fullLevel(temp.left, count + 1, height);
    } else {
        return height;
    }
}

问题是:“确定已满的最高级别，或者等效地，具有该级别的最大节点数。” - 必须使用递归。谢谢!

我不擅长递归，所以提前道歉!

Answer 1

就比较每个级别中实际 child 的数量与该级别可能的 child 数量而言，您走在了正确的轨道上。理想的方法是使用队列执行级别顺序遍历并返回最高的完整级别。但是，由于您坚持使用递归，问题就变成了在递归调用中保持水平计数的问题之一。一个天真的解决方案是为每个高度创建一个计数列表，然后返回该列表中的最后一个完整级别。

只有当两个 child 都存在时，优化才会递归——显然，如果缺少一个 child ，就不可能在树中有更深的完整级别，我们可以结束搜索。

public static int fullLevel(Node root) {
    ArrayList<Integer> levelCounts = new ArrayList<>();
    levelCount(root, 0, levelCounts);

    for (int i = levelCounts.size() - 1; i >= 0; i--) {
        if ((int)Math.pow(2, i) == levelCounts.get(i)) {
            return i;
        }
    }

    return -1;
}

private static void levelCount(Node root, int height, ArrayList<Integer> levelCounts) {
    if (root != null) {
        if (height >= levelCounts.size()) {
            levelCounts.add(0);
        }

        levelCounts.set(height, levelCounts.get(height) + 1);

        if (root.left != null && root.right != null) {
            levelCount(root.left, height + 1, levelCounts);
            levelCount(root.right, height + 1, levelCounts);
        }
    }
}

以下示例树的输出为 2(零索引):

       ____1____
      /         \ 
    _2_        __3__
   /   \      /     \
  4     5    6      _7_    <-- tallest full level
 / \   /    / \    /   \
8   9 10   11  12 13   14

Try it!