c# - 二叉搜索树的高度迭代

我尝试了一种迭代方法来找到二叉搜索树的高度/深度。
基本上，我尝试使用广度优先搜索来计算深度，使用队列来存储树节点，使用整数来保存树的当前深度。树中的每个节点都排队，并检查其子节点如果存在子节点，则深度变量将递增代码如下：

public void calcDepthIterative() {
    Queue<TreeNode> nodeQ = new LinkedList<TreeNode>();
    TreeNode node = root;
    int level = 0;
    boolean flag = false;

    nodeQ.add(node);
    while(!nodeQ.isEmpty()) {
        node = nodeQ.remove();
        flag = false;
        if(node.leftChild != null) {
            nodeQ.add(node.leftChild);
            flag = true;
        }

        if(node.rightChild != null) {
            nodeQ.add(node.rightChild);
            flag = true;
        }
        if(flag) level++;
    }
    System.out.println(level);

}

然而，代码并不适用于所有情况。例如，对于以下树：

     10
   /    \
  4      18
   \    /  \
    5  17   19

它将深度显示为3，而不是2。
我做了另一个版本，使用一个额外的队列来存储当前深度，使用this page中的思想。我想避免使用额外的队列，所以我试图优化它。下面是可以工作的代码，尽管使用了额外的队列。

public void calcDepthIterativeQueue() {
    Queue<TreeNode> nodeQ = new LinkedList<TreeNode>();
    Queue<Integer> lenQ = new LinkedList<Integer>();

    TreeNode node = root;
    nodeQ.add(node);
    lenQ.add(0);
    int maxLen = 0;
    while(!nodeQ.isEmpty()) {
        TreeNode curr = nodeQ.remove();
        int currLen = lenQ.remove();
        if(curr.leftChild != null) {
            nodeQ.add(curr.leftChild);
            lenQ.add(currLen + 1);
        }

        if(curr.rightChild != null) {
            nodeQ.add(curr.rightChild);
            lenQ.add(currLen + 1);
        }
        maxLen = currLen > maxLen ? currLen : maxLen;
    }
    System.out.println(maxLen);

}

问题：
有没有办法修复第一个方法，使其返回正确的深度？
编辑
见下面接受的答案
rici答案的Java代码：

public void calcDepthIterative() {
    Queue<TreeNode> nodeQ = new LinkedList<TreeNode>();
    int depth = 0;
    nodeQ.add(root);
    while(!nodeQ.isEmpty()) {
        int nodeCount = nodeQ.size();
        if(nodeCount == 0)
            break;
        depth++;
        while(nodeCount > 0) {
            TreeNode topNode = nodeQ.remove();
            if(topNode.leftChild != null)
                nodeQ.add(topNode.leftChild);
            if(topNode.rightChild != null)
                nodeQ.add(topNode.rightChild);
            nodeCount--;
        }
    }
    System.out.println(depth);
}

最佳答案

有一种方法：

Create a Queue, and push the root onto it.
Let Depth = 0
Loop:
    Let NodeCount = size(Queue)
    If NodeCount is 0:
        return Depth.
    Increment Depth.
    While NodeCount > 0:
        Remove the node at the front of the queue.
        Push its children, if any, on the back of the queue
        Decrement NodeCount.

工作原理
每次设置NodeCount时，扫描就要开始新的行。nodeCount设置为该行中的节点数。当所有这些节点都被删除（即NodeCount递减为零）时，该行已完成，并且该行上所有节点的子节点都已添加到队列中，因此该队列再次具有完整的行，NodeCount再次设置为该行中的节点数。

关于c# - 二叉搜索树的高度迭代，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15013956/