返回二叉查找树的高度

Question

我有两个类，BSTSet和BSTNode，它们都有一个可以返回高度的height（）方法。我得到一个stackoverflow错误，并不确定是什么导致它。

BSTSet

public class BSTSet <E extends Comparable<E>> extends AbstractSet <E> { 

    // the root of the supporting binary search tree 
    private BSTNode<E> root; 

    // number of elements in the set 
    private int count = 0; 

    public boolean isEmpty() { 
     return count == 0; 
    } 

    public int size() { 
     return count; 
    } 


    public int height() { 
     if(root == null) return -1; 
     else return root.height(); 
    } 
} 

BSTNode

public class BSTNode <E extends Comparable<E>> { 

    private E value; 
    private BSTNode<E> left; 
    public BSTNode<E> right; 

    public BSTNode(E value) { 
     this.value = value; 
    } 

    public E getValue() { 
     return value; 
    } 

    public BSTNode<E> getLeft() { 
     return left; 
    } 

    public BSTNode<E> getRight() { 
     return right; 
    } 

    public int height() { 
     if(left == null && right == null) return 0; 
     if(left != null && right == null) {UI.println("left");return left.height()+ 1; } 
     else if(right != null && left == null){UI.println("right");return right.height()+ 1;} 
     else{UI.println("both"); return Math.max(right.height(), left.height()) + 1;} 
    } 
} 

如果您想了代码或不再需要的信息，请随时提问。

Answer 1

if(left == null && right == null) return 0;

变化

if(left == null && right == null) return 1;

如果一个节点没有孩子仍然具有高度1

然后，只需做一个递归调用这样 else return Max(left.height(), right.tHeight) + 1;

根据定义，高度节点的t是它的最大高度是子发辫+ 1

堆栈溢出是由于调用height()方法相同的节点在这里：

else if(left != null && right == null || left == null && right != null) return height()+ 1; 
else return height()+ 2; 

我只是想扔这如果你想一个节点，在高度0开始明显保持 if(left == null && right == null) return 0;

Answer 2

的问题是，你的递归height()方法调用thisheight()。这不是算法应该如何工作的原因，它是无限递归循环的明显原因，它会给你堆栈溢出。

@ xgeorgekx的方法应该给出正确的答案，但我不相信它是最优的。如果树是平衡的，那么左边和右边的子树的高度是相关的......并且你可能不需要穿过两边。如果可以避免，那么height方法可以实现为O(logN)而不是O(N)。

我怀疑你原来的做法是试图将O(logN) ...