0

我正在尝试创建一种方法来告诉我二叉树的高度，最简单的方法是使用递归，但是由于某种原因，我的一个变量正在重置，即使我认为我正在检查，所以它会保持不变...
这是我的代码

template<class T>
int findHeight(binaryTreeNode<T> , int leftHeight, int rightHeight,
        int maxHeight) {
    if (leftHeight >= rightHeight && leftHeight >= maxHeight) {
        maxHeight = leftHeight;
    }
    else if (leftHeight < rightHeight && rightHeight >= maxHeight) {
        maxHeight = rightHeight;
    }
    if (t != NULL) {
        cout << "current leftHeight " << leftHeight << " current rightHeight "
                << rightHeight << " current maxHeight " << maxHeight << endl;

        findHeight(t->leftChild, ++leftHeight, rightHeight, maxHeight);
        findHeight(t->rightChild, leftHeight, ++rightHeight, maxHeight);
    }
    return ++maxHeight;
}

这是我尝试这个时得到的输出：

current leftHeight 0 current rightHeight 0 current maxHeight 0
current leftHeight 1 current rightHeight 0 current maxHeight 1
current leftHeight 2 current rightHeight 0 current maxHeight 2
current leftHeight 2 current rightHeight 1 current maxHeight 2
current leftHeight 1 current rightHeight 1 current maxHeight 1
current leftHeight 2 current rightHeight 1 current maxHeight 2
current leftHeight 3 current rightHeight 1 current maxHeight 3
Returned value = 1

谁能帮帮我吗？我怎样才能做到这一点，以便 maxHeight 不会被重置，并且会在整个递归过程中随时保持找到的最大值。

4

2 回答 2

2

事情更简单：

int findHeight(binaryTreeNode<T> *t){
    return t ? 1 + MAX(findHeight(t->leftChild), findHeight(t->rightChild)) : 0;
}

在您的代码中，您遇到了问题，因为maxheight它是按值传递的，而不是按引用传递的。

于 2012-10-21T04:22:33.220 回答
0

A function parameter has automatic storage duration (commonly called "on the stack"). This means each call to findHeight has its own variable named maxHeight. You increment one of these local variables right before its lifetime ends. And although you return the incremented value, you don't use that return value in the recursive calls.

Either use a reference parameter, or use the return values from the two recursive calls.

于 2012-10-21T04:27:21.377 回答