如何找到BST的高度反复？ [英] How to find height of BST iteratively?

问题描述

  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 b $ b 15分配
14
13
有什么问题。根据树的这一系列高6在那里为我的代码是显示5。

I wrote iterative method, to calculate height of tree. but in some cases its not working properly. As in case: 10 1 2 3 4 5 18 17 16 15 14 13 what's the problem. according to this sequence height of tree is 6 where as my code is showing 5.

推荐答案

您使用的是两个回路，但每个循环只调查了节点的oneside，但在树中的每个节点都具有两面性，你应该调查这一切。你可以做到这一点通过递归调用。

You are using two loops, but each loop investigated only oneside of node, but each node in tree has two sides you should investigate it all. You can do it through recursion call.

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);
}

迭代版本：

Iterative version:

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);
}

这篇关于如何找到BST的高度反复？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！