时间戳

首页 > 解决方案 > javascript：使用递归方法将二叉树值推入数组

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

问题描述

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

  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]

我的代码哪里出错了？

标签： javascriptbinary-search-treeinorder

解决方案

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

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

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

  return nodes;
}

在这段代码中，dfsInOrder...

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

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

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

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

...这对我来说很好，但调试起来有点困难。

推荐阅读