二叉搜索树的递归到迭代方法

Question

我正在进行一项作业，使用递归方法中的迭代方法获取 BST 的高度。下面将是提供的递归代码和我的代码。它返回一个比实际高度大的高度。例如，高度假设为 4，但它 returns 5.

//Provided code 
public  int getHeight() {
    return getHeight(root);
}

private int getHeight(Node node) {
    if (node==null) {
        return -1;
    } else {
        int leftHeight = getHeight(node.left);
        int rightHeight = getHeight(node.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

//my code
public int getHeightI() {
    return getHeightI(root);
}

private int getHeightI(Node node) {
    Node curr = node;
    int leftHeight = 0;
    int rightHeight = 0;
    if (curr!=null) {
        while (curr.left!=null) {
            leftHeight++; 
            curr = curr.left;
        } 
        while (curr.right!=null) {
            rightHeight++; 
            curr = curr.right; 
        }
    }   
    return Math.max(leftHeight, rightHeight)+1;
}

Answer 1

您的代码返回的树高比树的实际高度高一。我建议你使用这个代码

int height(tree* root)
{
if(!root)
{ return -1;
}
else{
return __max(root->left,root->right);
}

希望你明白你的错误。