非递归地查找 BST 的高度？

Question

这是一种寻找高度的递归方法，但是我的二叉搜索树中有非常多的节点，我想找到树的高度，并将高度分配给每个单独的子树。所以递归方法抛出stackoverflow异常，我如何做到这一点，非递归和不使用堆栈?

private int FindHeight(TreeNode node)
    {
        if (node == null)
        {
            return -1;
        }
        else
        {
            node.Height = 1 + Math.Max(FindHeight(node.Left), FindHeight(node.Right));
            return node.Height;
        }
    }

我相信我必须使用后序遍历，但没有堆栈?

Answer 1

我能够使这个方法，它确实返回正确的高度，但它分配每个节点的深度，而不是高度。

 public void FindHeight()
    {
        int maxHeight = 0;
        Queue<TreeNode> Q = new Queue<TreeNode>();
        TreeNode node;
        Q.Enqueue(Root);
        while (Q.Count != 0)
        {
            node = Q.Dequeue();
            int nodeHeight = node.Height;
            if (node.Left != null)
            {
                node.Left.Height = nodeHeight + 1;
                Q.Enqueue(node.Left);
            }
            if (node.Right != null)
            {
                node.Right.Height = nodeHeight + 1;
                Q.Enqueue(node.Right);
            }
            if (nodeHeight > maxHeight)
            {
                maxHeight = nodeHeight;
            }
        }
        Console.WriteLine(maxHeight);
    }