javascript：使用递归方法将二叉树值推入数组

Question

我正在尝试使用顺序遍历和递归方法遍历二叉搜索树。我的目标是将每个节点的值推入一个数组并 return 它。这是我的代码：

  dfsInOrder(node=this.root) {
    let nodes = []
    if(node === null) return 


    nodes.push(this.dfsInOrder(node.left))
    nodes.push(node.val)
    nodes.push(this.dfsInOrder(node.right))
    return nodes
  }

以下是我将数据插入树中的方式：

binarySearchTree
  .insert(15)
  .insert(20)
  .insert(10)
  .insert(12);

为清楚起见，树的根值为 15，而 10 和 12 都在树的左侧。 20在右边。

我正在寻找这样的结果：

[12,10,15,20]

但我得到的是：

[Array(3), 15, Array(3)].....


[undefined, 10, Array(3)]
15
[undefined, 20, undefined]

我的代码哪里出错了？

Answer 1

这是解决此问题的一种方法：

dfsInOrder(node=this.root) {
  const nodes = [];

  if (node !== null) {
    nodes.push(
      ...this.dfsInOrder(node.left),
      node.val,
      ...this.dfsInOrder(node.right)
    );
  }

  return nodes;
}

在此代码中，dfsInOrder...

总是returns 平面数组，边缘为空。从类型检查的角度来看，这稍微好一些，但也允许过滤掉你现在看到的这些 undefined 值
将递归调用的结果（通过 ... 运算符）插入结果数组时，总是将它们展平

作为旁注，push 不会更改您的数组引用，因此无需在此处使用 let。其实这个函数可以重写，完全避免中间变量：

dfsInOrder(node=this.root) {
  if (node === null) return [];

  return [
    ...this.dfsInOrder(node.left),
    node.val,
    ...this.dfsInOrder(node.right),
  ];
}

...这对我来说没问题，但调试起来有点困难。

javascript：使用递归方法将二叉树值推入数组

javascript: pushing binary tree values into an array using the recursion method

javascript

binary-search-tree

inorder