Javascript 与 Python 中的递归深度优先搜索

Question

所以我在AlgoExpert上做算法题，遇到了递归DFS算法。最初我尝试在 JavaScript 中解决它，但遇到了问题。当我看代码走查时，我发现它的解决方式非常简单。

这里是 Python 解决方案：

def depthFirstSearch(self, array):
    array.append(self.name);
    for child in self.children:
        child.depthFirstSearch(array);
    return array

我的问题是，您如何在 JavaScript 中实现同样的目标？我尝试这样做：

function depthFirstSearch(array) {
    array.push(this.name);
    for(let i=0; i < array.length; i++) {
        depthFirstSearch(array[i]);
    };
    return array;
}

我一直收到错误消息：

depthFirstSearch is not defined

我很困惑为什么在 JavaScript 中尝试递归调用函数本身时出现错误？

这是整个代码片段：

class Node {
    constructor(name) {
        this.name = name;
        this.children = [];
    }

    addChild(name) {
        this.children.push(new Node(name));
        return this;
    }

    depthFirstSearch(array) {
       /*
        * Step 1: Add the root node to the array
        *                   this.name is the root at the start
        * Step 2: Check that the left child node isn't null
        * Step 3: If the left child node isn't null, Add the left child node to the array
        * Step 4: If the left child node is null check the right child node
        * Step 5: If the right child node isn't null, add the right child node to the array
        * Step 6: Repeat steps 1-5 until there are no nodes left to check
        */
        array.push(this.name);
        const children = this.children;
        for(let i=0; i < array.length; i++) {
            depthFirstSearch(array[i]);
        };
        return array;
    }
}

Answer 1

几个问题：

depthFirstSearch是Nodeclass的方法，不是全局函数，所以应该在节点实例上调用。因此，例如，如果您有一个名为 child 的节点，它应该被称为 child.depthFirstSearch
由于它是一种方法，因此不应使用 function 关键字（在 class 结构中）。这已在您问题中的最后一个代码块中正确删除。
传递给depthFirstSearch的参数应该是一个数组，但是你传递给它的array[i]是一个节点。它应该只是 array，如 Python 代码中那样。
循环不应该超过 array，而是超过当前节点的 children，即超过 this.children。所以你的 for 循环中会有 i < this.children.length。

一些其他备注：

for 循环后不需要分号。添加它实际上引入了一个（无害的）空语句。
使用 for..of 而不是普通的旧 for 循环使代码更短一些，也能更好地模仿 Python 代码的作用。

更正版本：

class Node {

    /* ... the other code ... */

    depthFirstSearch(array) {
        array.push(this.name);
        for (let child of this.children) {
            child.depthFirstSearch(array);
        }
        return array;
    }
}

Javascript 与 Python 中的递归深度优先搜索

Recursive Depth First Search in Javascript vs Python

javascript

python

algorithm

depth-first-search

data-structures