c - 如何在不使用递归和层序遍历的情况下求二叉树的高度？

Question

我想到了前序遍历来查找树的高度。

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 直到最左边的节点，然后，如果我向上移动，我减少它以防我需要向右移动，然后重复整个练习。对吗？

Answer 1

考虑下面的树 -

    o
   / \
  o   o
 /     \
o       o 

您将到达 c==2 的最左边分支的末尾，然后在向上的路上弹出节点，但只为具有右子节点的节点递减 c，而实际上您应该递减它出现在每个流行音乐上，因为这意味着您升级了，而不管其他 child 。在这种情况下，您将到达顶部节点，递减一次，然后从 c==1 的根开始下降，最终到达 3。

如果您删除条件，它应该会起作用。或者，您可以保留每个级别的 c 的值，而不是通过递减来恢复它 - 您可以将它插入与节点指针一起的单独堆栈，或者您可以将代码转换为递归的，以 c(和当前节点)作为局部变量(基本上这是一回事，除了编译器为您维护堆栈)。