二叉搜索树的高度迭代 [英] Height of binary search tree iteratively

问题描述

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

I was trying out an iterative method to find the height/depth of a binary search tree. Basically, I tried using Breadth First Search to calculate the depth, by using a Queue to store the tree nodes and using just an integer to hold the current depth of the tree. Each node in the tree is queued, and it is checked for child nodes. If child nodes are present, then the depth variable is incremented. Here is the code:

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

}

但是，该代码不适用于所有情况。例如，对于以下树：

However, the code doesn't work for all cases. For example, for the following tree:

     10
   /    \
  4      18
   \    /  \
    5  17   19

深度显示为3，而不是2.
我使用此页面。我想避免使用额外的队列，所以我尝试对其进行优化。这是有效的代码，尽管使用了额外的队列。

It shows the depth as 3, instead of 2. I did an alternate version of it using an additional Queue to store the current depths, using the idea in this page. I wanted to avoid using an additional queue so I tried to optimize it. Here is the code which works, albeit using an additional 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);

}

问题：

是否可以解决第一种方法，使其返回正确的深度？

Is there a way to fix the first method such that it returns the right depth?

编辑
下面看到接受的答案

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.

工作原理

每次<设置了code> NodeCount ，扫描即将开始新的一行。 NodeCount设置为该行中的节点数。删除所有这些节点后（即NodeCount递减为零），则该行已完成，并且该行上所有节点的子节点都已添加到队列中，因此该队列再次具有完整的行，然后将NodeCount再次设置为该行中的节点数。

How it works

Every time NodeCount is set, the scan is just about to start a new row. NodeCount is set to the number of Nodes in that row. When all of those Nodes have been removed (i.e., NodeCount is decremented to zero), then the row has been completed and all the children of nodes on that row have been added to the queue, so the queue once again has a complete row, and NodeCount is again set to the number of Nodes in that row.

这篇关于二叉搜索树的高度迭代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！