tree - 倾斜二叉树

Question

1) 术语不平衡二叉树是什么意思，我们如何编写算法来测试它？

2）我有一个问题，要求编写一个函数来测试二叉树的深度。我认为这会起作用，但不确定....：

function getDepth(Node n){
    if(node == null){
        return 0;
    }
    return 1 + Math.max(getDepth(node.left), getDepth(node.right));
}
getDepth(root);

谁能给我指点...

Answer 1

1) 倾斜二叉树不是一个 100% 广泛使用的通用术语（甚至 Google 也会感到困惑）。搜索你的讲义或书籍，看看它们的含义。

1. 要测试一棵树是否具有与节点一样多的级别，您可以只使用您已经拥有的计算级别的函数和另一个函数来计算节点的数量。

   但是，如果发现节点数不能与级别数相同，您应该创建另一个更有效的算法，该算法会提前终止。

2. 深度函数是正确的。毕竟，这不是直接取自树深度的定义吗？

   （唯一可能的 nitpick 是 depth(null) = 1。只要确保你不需要 depth(null) = 0 代替）

Answer 2

倾斜二叉树是只有一种子树的树。如果一棵树只有左子树，那么它就是左倾斜树，反之亦然。