深度优先搜索（递归）到达叶节点后如何工作？

Question

当前正在学习DFS，但对它的工作原理只有几个问题。

由于代码的冗长性，下面的Repl链接：

https://repl.it/@Stylebender/DFS-Recursive

1. traverseInOrder函数的基本情况只是“返回列表”吗？

2. 正如您在第45行中看到的那样，并且在运行代码时（控制台记录遍历节点的路径），我知道JS递归地从9 => 4 => 1下降，因为仍然有一个向左节点。

我的问题是，为什么以及如何从节点1遍历到节点6？换句话说，traverseinOrder函数如何能够将节点6作为1之后的参数来接收？]

Answer 1

我复制第39至55行以使答案易于理解：

DFTInOrder(){
   return traverseInOrder(this.root, []);
 } 
}

//Note, base case occurs where the node within the function no longer has any children.
function traverseInOrder(node, list){
 console.log(node.value);
 if(node.left) {
   traverseInOrder(node.left, list);
 }
 list.push(node.value);
 if(node.right) {
   traverseInOrder(node.right, list);
 }
 return list;
}

1. 否，traverseInOrder更新list参数，然后将其返回。如第39行所示，初始列表为空。然后，对于每个traverseInOrder的调用，在遍历左分支的节点之后和遍历右分支的节点之前，将node.value添加到列表中。基本情况（当左右为空时）为：

将node.value添加到当前的list中。[[然后返回此list。

这里有一个陷阱，因为您使用
2. in-ordering遍历了节点，但是使用pre-ordering记录了它们。查看使用以下参数调用traverseInOrder时会发生什么：Node(4)和list=[]：

    function traverseInOrder(node, list){
      console.log(node.value); // log 4
      if(node.left) { // 1
        traverseInOrder(node.left, list); 
        // log 1
        // add 1 to the list (since 1.left and 1.right are null)
      }
      list.push(node.value); // add 4 to the list
      if(node.right) { // 6
        traverseInOrder(node.right, list); 
        // log 6
        // add 6 to the list (since 6.left and 6.right are null)
      }
      return list;
    }

因此遍历顺序：1, 4, 6。但是您记录了节点4, 1, 6。