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

Question

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

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

Answer 1

这是一种实现方式:

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 再次设置为该行中的节点数。