2

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

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。我使用此页面中的想法使用附加队列存储当前深度做了一个替代版本。我想避免使用额外的队列，所以我尝试优化它。这是有效的代码，尽管使用了额外的队列。

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

3 回答 3

6

这是一种方法：

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

于 2013-02-22T02:13:16.493 回答
1 
public int height(Node root){
  int ht =0;
  if(root==null) return ht;
  Queue<Node> q = new ArrayDeque<Node>();
  q.addLast(root);
  while(true){
      int nodeCount = q.size();
      if(nodeCount==0) return ht;
      ht++;
      while(nodeCount>0){
       Node node = q.pop();
       if(node.left!=null) q.addLast(node.left);
       if(node.right!=null) q.addLast(node.right);
       nodeCount--;
      }
 }
于 2014-04-15T09:02:36.947 回答
-3

递归如何，

int Depth(Node node)
{
    int depthR=0,depthL=0;
    if(Right!=null)depthR=Depth(Right);
    if(Left!=null)depthL=Depth(Left);
    return Max(depthR,depthL)+1;
}

如果你想要一个基于零的深度，只需将结果深度减去 1。

于 2013-02-22T05:29:37.973 回答