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具有右子节点的节点递减，而实际上您应该在每次弹出时递减它，因为这意味着您进入了一个级别起来，不管别的孩子。在这种情况下，您将到达顶部节点，递减一次，然后以 c==1 从根开始递减，最终达到 3。

如果您删除条件，它应该可以工作。或者，您可以保留c每个级别的值，而不是通过递减来恢复它 - 您可以将其推送到节点指针旁边的单独堆栈中，或者您可以将代码转换为递归，使用c（和当前节点）作为局部变量（基本上这是同一件事，除了编译器为您维护堆栈）。