将二叉树遍历到给定深度？

Question

我必须将二叉树遍历到给定深度，然后确定该深度之后的节点数，但我在确定如何遍历到给定深度时遇到了一些问题。我目前所拥有的是。

public static int sizeBelow (Node x, int y) {
    if (t == null) {
    return 0;

}else{

    int count = 0;
    int leftDepth = 0;
    int rightDepth = 0;

  if(leftDepth < y){
    leftDepth=1+sizeBelow(x.left, y);
  }else{
    count=1+sizeBelow(x.left,y);
  }

  if(rightDepth < y){
    rightDepth= 1+sizeBelow(x.right,y);
  }else{
    count=1+sizeBelow(x.right,y);
  }
  return count;
}

我可能在递归方面做错了什么，但我的想法是如果左边或右边的深度不等于给定的深度，然后增加深度并再次运行。如果它处于正确的深度，那么它应该将计数加 1 并继续。

Answer 1

在我们研究如何做到这一点之前，让我们逐行分析下面的代码...

public static int sizeBelow (Node x, int y) { // y is very ambiguous 
    if (t == null) {// I am guessing t should be x
    return 0;

}else{

    int count = 0; // the number of nodes below the depth barrier y
    int leftDepth = 0; // this will always be 0 since you never alter it
    int rightDepth = 0; // this to

  if(leftDepth < y){ // this will never not go off unless y is 0 
    leftDepth=1+sizeBelow(x.left, y); // we must decrement y
  }else{ // or we will never enter here 
    count=1+sizeBelow(x.left,y);  // this should be + =
  }

  if(rightDepth < y){ // this will also never not go off
    rightDepth= 1+sizeBelow(x.right,y); // y is again not decremented
  }else{ // this will never be reached
    count=1+sizeBelow(x.right,y); // this to
  }
  return count;
}

你必须明白，在递归中，每个函数调用都使用恰好具有相同名称的新变量，递归调用中永远不会考虑左右深度的变化，除非你传入它们。

这是我修改后的代码

public static int sizeBelow (Node x, int depth) {  
    if (x == null) {
    return 0;

}else{
  int count = 0; 
  if(depth == 0){
    count +=sizeBelow(x.left, (depth - 1)); 
    count +=sizeBelow(x.right, (depth - 1)); 
  }else{  
    count +=1+sizeBelow(x.left,depth);  
    count +=1+sizeBelow(x.right,depth);
  }


  return count;
}

Answer 2

您可以使用深度/广度优先搜索来搜索二叉树。但做一些改变：

在函数外创建一个变量：

int count = 0;

向您的递归函数添加一个额外的布尔参数：

public static int sizeBelow(Node x, boolean afterNode){

点击节点后，使用 if 语句并将布尔值设置为 true：

if(currentNode == x || afterNode){

    return sizeBelow(currentNode.right, true);

else{

    return sizeBelow(currentNode.right, false);

左边用同样的方法child

然后添加条件：

if(afterNode){

    if(currentNode.right != null){
        count++;
    }

}

对左侧 child 再次应用相同的方法。

你看到方法了吗？

您可以使用任何二叉树搜索算法

将二叉树遍历到给定深度？

Traversing a binary tree up to a given depth?

java

recursion

binary-tree