递归实现二叉树层序遍历未输出指定节点及空判断问题解析

问题涉及代码 #

JavaScript代码 #

// Recursive javascript program for level
// order traversal of Binary Tree

// Class containing left and right child of current
// node and key value
class Node {
  constructor(val) {
    this.data = val;
    this.left = null;
    this.right = null;
  }
}


// Root of the Binary Tree
var root = null;

// Function to print level order traversal of tree
function printLevelOrder() {
  var h = height(root);
  var i;
  // for (i = 1; i <= h; i++)
  printCurrentLevel(root, h);
}

// Compute the "height" of a tree -- the number
// of nodes along the longest path
// from the root node down to the farthest leaf node.
function height(root) {
  if (root == null)
    return 0;
  else {
    // Compute height of each subtree
    var lheight = height(root.left);
    var rheight = height(root.right);

    // Use the larger one
    if (lheight > rheight)
      return (lheight + 1);
    else
      return (rheight + 1);
  }
}

// Print nodes at the current level
function printCurrentLevel(root, level) {

  //  alert("root data = "+root.data+" : level = "+level);


  document.getElementById("demo").innerHTML = document.getElementById("demo").innerHTML + "<br/>" + "root data = " + root.data + " : level = " + level + "";



  if (root == null)
    return;
  if (level == 1) {
    //alert(root.data);

  } else if (level > 1) {

    printCurrentLevel(root.left, level - 1);
    printCurrentLevel(root.right, level - 1);
  }
}

// Driver program to test above functions

root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);

root.left.left.left = new Node(8);
root.left.left.right = new Node(9);



console.log("Level order traversal of  binary tree is ");
printLevelOrder();

HTML代码 #

<!DOCTYPE html>
<html>

<body>

  <h2>My First JavaScript</h2>


  <p id="demo"></p>

</body>

</html>

运行现象 #

运行代码后，输出结果如下：

root data = 1 : level = 4
root data = 2 : level = 3
root data = 4 : level = 2
root data = 8 : level = 1
root data = 9 : level = 1
root data = 5 : level = 2

出现两个异常：

• 未出现预期的root data = 3: level = 3输出；
• 若将printCurrentLevel函数中的if (root == null) return;语句注释掉，输出仅为root data = 1 : level = 4。

现象原因解释 #

1. 为什么没有输出root data = 3: level = 3？ #

问题出在代码执行顺序和错误中断上：

• 首先计算出二叉树高度为4（根节点1到叶子节点8/9的路径长度），printLevelOrder仅调用了一次printCurrentLevel(root, 4)；
• printCurrentLevel函数先执行DOM输出语句，再判断节点是否为空。当递归遍历完左分支（1→2→4→8/9→空节点）时，会进入printCurrentLevel(null, 0)，此时访问null.data会直接抛出TypeError，脚本中断；
• 中断前，处理根节点右分支（节点3）的递归逻辑还没执行，因此不会输出root data = 3: level = 3。

2. 注释掉if (root == null) return;后，为什么只有root data = 1 : level = 4？ #

• 注释空节点判断后，执行printCurrentLevel(1,4)输出节点1的信息，接着进入level>1分支调用printCurrentLevel(2,3)；
• 调用printCurrentLevel(2,3)时，先执行DOM输出语句，但后续递归到空节点时，访问null.data会立即抛出TypeError，整个脚本直接终止，后续所有递归调用都无法执行，最终只保留第一次的输出内容。

补充：正确的写法应该把if (root == null) return;放在DOM输出语句之前，这样空节点会直接返回，避免报错，同时保证所有分支的递归逻辑能完整执行。

内容的提问来源于stack exchange，提问作者Jagan