歪斜二叉树

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. 深度功能正确。毕竟，这不是直接取自树深度的定义吗?

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

Answer 2

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