迭代地二叉搜索树的高度

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.我使用此页面中的想法使用额外的队列来存储当前深度的替代版本.我想避免使用额外的队列,所以我试图优化它.这是有效的代码,尽管使用了额外的Queue.

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