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

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.

回答1:

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

回答2:

There is a way that does not require any extra space except the queue for storing the nodes.

1. Add child nodes of a current element and remember size of the queue.
2. Let each dequeue call decrement the counter
3. When counter reaches zero that means we are done with current level.
4. Repeat and count number of times counter reaches zero - this is the depth/height of the tree

Code goes like this :

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

Time complexity is O(N), space complexity is O(N)

回答3:

The problem:

You are finding the depth of the left-most node in the first loop, and the right-most in the second, and never interrogating any node that involves going down to the left AND the right.

A solution:

Have a single loop that drills down the left nodes, but adds each right node that it 'skips' into a queue. When you run out of left nodes, pop-off a node form your queue and continue on until the queue becomes empty. You'll need to store the height of each node you put in the queue with that node.

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