我想出了遍历遍历的方法来找到树的高度。
void preHeight(node * n)
{
int max = 0,c = 0;
while(1)
{
while(n)
{
push(n);
c++;
if(c>max)
max = c;
n= n->left;
}
if (isStackEmpty())
return max;
n = pop();
if(n->right) //Problem point
c--;
n=n->right;
}
}
我得到的高度正确，但是我不确定我的方法是否正确。我要做的是将计数器c增加到最左边的节点，然后，如果我向上移动，我会减小它，以防万一我需要向右移动，然后重复整个练习。那是对的吗？
考虑下面的树-
o
/ \
o o
/ \
o o
您将以c == 2到达最左边分支的末尾，然后向上弹出节点，但仅对c带有右子节点的节点递减，而实际上您应该在每次弹出时递减它，因为这意味着您已上一级起来，不管其他孩子。在这种情况下，您将到达顶部节点，递减一次，然后以c == 1从根开始下降，最终达到3。
如果您删除该条件，它将正常工作。或者，您可以保留c每个级别的值，而不用递减的方式恢复它-您可以将其与节点指针一起推入单独的堆栈中，也可以使用c（和当前节点）将代码转换为递归作为局部变量（基本上是同一回事，只是编译器会为您维护堆栈）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句