如何迭代求出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);
    }

我写的迭代法，计算树的高度。但在某些情况下，它不能正常工作。例如:10123.45181716151413有什么问题吗?根据这个序列，树的高度是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);
}

Answer 2

有一种方法不需要任何额外的空间，除了用于存储节点的队列。

1. 添加当前元素的子节点并记住队列的大小。
2. 让每个队列调用递减计数器
3. 当计数器达到零时，意味着我们完成了当前电平。
4. 重复并计数计数器达到零的次数-这是树的深度/高度

代码是这样的:

public int treeDepth(Node root){
    int height = 0;
    int counterNodesInLevel = 1;
    if(root!=null)
    {
        Queue<Node> queue=new Queue<Node>()
        queue.enqueue(root);
        while (!queue.isEmpty()){
            Node current = queue.dequeue();
            counterNodesInLevel -= 1;
            if(current.left!=null){
               queue.enqueue(current.left)
            }
            if(current.right!=null){
               queue.enqueue(current.right)
            }
            if (counterNodesInLevel == 0){
                height += 1;
                counterNodesInLevel = queue.Size();
            }                    
        }    
    }    
    return height;
}    

时间复杂度为O(N)，空间复杂度为O(N)

Answer 3

问题:

你在第一个循环中找到最左边节点的深度，在第二个循环中找到最右边节点的深度，并且从不询问任何涉及向左和向右的节点。

一个解决方案:

设置一个单循环，下钻左侧节点，但将每个"跳过"的右侧节点添加到队列中。当用完左边的节点时，从队列中弹出一个节点，然后继续操作，直到队列变为空。您需要用该节点存储队列中每个节点的高度。

Answer 4

public int Height()
    {
        int result = GetMaxHeight(this.Root,0);
        return result;
    }
    private int GetMaxHeight(Node<T> node,int count)
    {
        int leftMax = 0, rightMax = 0;
        if (node.Left != null)
        {
            leftMax = GetMaxHeight(node.Left, count+1);
        }
        if (node.Right != null)
        {
            rightMax = GetMaxHeight(node.Right, count + 1);
        }
        if(node.Left==null && node.Right == null)
        {
            return count;
        }
        return Math.Max(leftMax,rightMax);
    }