如何迭代地找到BST的高度？

Question

  public void HeightIterative()
    {
        int counter = 0;
        int counter2 = 0;
        TreeNode current=root;

        if(current != null)
        {
            while(current.LeftNode!=null)
            {
                counter++;
                current = current.LeftNode;
            }
            while(current.RightNode!=null)
            {
                counter2++;
                current = current.RightNode;
            }
        }

        int res = 1+Math.Max(counter, counter2);
        Console.WriteLine("The Height Of Tree Is: "+res);
    }

我写了迭代方法，来计算树的高度。但在某些情况下，它无法正常工作。如案例： 10 1 2 3 4 5 18 17 16 15 14 13 有什么问题。根据此序列，树的高度为 6，而我的代码显示为 5。

Answer 1

您正在使用两个循环，但每个循环仅调查节点的一侧，但树中的每个节点都有两侧，您应该全部调查。您可以通过递归调用来完成。

private int GetLen(TreeNode node)
{
  var result = 0;

  if(node != null)
  {
    result = Math.Max(GetLen(node.LeftNode), GetLen(node.RightNode)) + 1;
  }

  return result;
}

public void HeightIterative()
{
  int res = GetLen(root);
  Console.WriteLine("The Height Of Tree Is: "+res);
}

迭代版本：

private class NodeInfo
{
  public NodeInfo(TreeNode node, int len)
  {
    Node = node;
    Len = len;
  }

  public TreeNode Node {get; private set;}
  public int Len {get; private set;}
}

public void HeightIterative()
{
    int maxLen = 0;

    var queue = new Queue<NodeInfo>();
    queue.Enqueue(new NodeInfo(root, 1));

    while (queue.Count > 0)
    {
        var item = queue.Dequeue();
        var current = item.Node;
        var currentLen = item.Len;

        if (current.LeftNode != null)
        {
            queue.Enqueue(new NodeInfo(current.LeftNode, currentLen + 1));
        }

        if (current.RightNode != null)
        {
            queue.Enqueue(new NodeInfo(current.RightNode, currentLen + 1));
        }

        if (currentLen > maxLen)
        {
            maxLen = currentLen;
        }
    }

    Console.WriteLine("The Height Of Tree Is: " + maxLen);
}