如何正确回溯深度优先搜索算法？
我正在尝试解决一个问题，即:在二叉树中找到特定节点的所有祖先。
Input: root, targetNode
Output: An array/list containing the ancestors
假设我们以上面的二叉树为例。我们希望找到节点4的祖先。输出应为3、5、2、4。如果节点为8，则输出为3、1、8
为了解决这个问题，我编写了一个实现DFS的函数。
var ancestor = function(root, target) {
var isFound = false;
const dfs = (node, curr) => {
if (node === null) {
return curr;
}
if (node.val === target.val) {
curr.push(node.val);
isFound = true;
return curr;
}
curr.push(node.val);
const left = dfs(node.left, curr);
if (!isFound) {
const right = dfs(node.right, curr);
curr.pop();
return right;
} else {
curr.pop();
return left;
}
}
console.log(dfs(root, []));
};但是它没有返回正确的输出。例如，如果targetNode是7，则输出是3，如果targetNode是8，则输出也是3。如果我删除行curr.pop()，输出也是无效的。对于targetNode 7，它是3，5，6，2，7。我想我找到了我犯错的地方。在回溯时，我在移除推入curr数组的节点时做了一些错误的事情。如果我传递一个字符串而不是数组，它会正确地打印输出。
var ancestor = function(root, target) {
var isFound = false;
const dfs = (node, curr) => {
if (node === null) {
return curr;
}
if (node.val === target.val) {
curr += node.val;
isFound = true;
return curr;
}
const left = dfs(node.left, curr + node.val + '->);
if (!isFound) {
const right = dfs(node.right, curr + node.val + '->);
return right;
} else {
return left;
}
}
console.log(dfs(root, ''));上面的代码使用字符串而不是数组正确地打印输出，如果我通过targetNode 7，输出是3->5->2->7我的问题是，如何正确地取消选择/回溯？或者我还有什么地方做得不对吗？提前谢谢。
回答 3
Stack Overflow用户
发布于 2021-11-11 17:31:43
自然设置中的递归
递归是一种函数式继承，因此将其与函数式风格一起使用会产生最佳结果。这意味着要避免像push和cur += node.val这样的突变，像isFound = true这样的变量重新赋值，以及其他副作用。我们可以将ancestor编写为一个简单的基于生成器的函数，它将每个节点预先设置为递归子问题的输出。
const empty =
Symbol("tree.empty")
function node(val, left = empty, right = empty) {
return { val, left, right }
}
function* ancestor(t, q) {
if (t == empty) return
if (t.val == q) yield [t.val]
for (const l of ancestor(t.left, q)) yield [t.val, ...l]
for (const r of ancestor(t.right, q)) yield [t.val, ...r]
}
const mytree =
node(3, node(5, node(6), node(2, node(7), node(4))), node(1, node(0), node(8)))
for (const path of ancestor(mytree, 7))
console.log(path.join("->"))
3->5->2->7使用模块
最后，我建议对这段代码使用基于模块的方法：
// tree.js
const empty =
Symbol("tree.empty")
function node(val, left = empty, right = empty) {
return { val, left, right }
}
function* ancestor(t, q) {
if (t == empty) return
if (t.val == q) yield [t.val]
for (const l of ancestor(t.left, q)) yield [t.val, ...l]
for (const r of ancestor(t.right, q)) yield [t.val, ...r]
}
function insert(t, val) {
// ...
}
function remove(t, val) {
// ...
}
function fromArray(a) {
// ...
}
// other tree functions...
export { empty, node, ancestor, insert, remove, fromArray }// main.js
import { node, ancestor } from "./tree.js"
const mytree =
node(3, node(5, node(6), node(2, node(7), node(4))), node(1, node(0), node(8)))
for (const path of ancestor(mytree, 7))
console.log(path.join("->"))3->5->2->7私有生成器
在前面的实现中，我们的模块为ancestor的公共接口公开了一个生成器。另一个选项是，当一个节点找不到并且没有祖先时，返回undefined。
const empty =
Symbol("tree.empty")
function node(val, left = empty, right = empty) {
return { val, left, right }
}
function ancestor(t, q) {
function* dfs(t) {
if (t == empty) return
if (t.val == q) yield [t.val]
for (const l of dfs(t.left)) yield [t.val, ...l]
for (const r of dfs(t.right)) yield [t.val, ...r]
}
return Array.from(dfs(t))[0]
}
const mytree =
node(3, node(5, node(6), node(2, node(7), node(4))), node(1, node(0), node(8)))
const result =
ancestor(mytree, 7)
if (result)
console.log(result.join("->"))
else
console.log("no result")
3->5->2->7Stack Overflow用户
发布于 2021-11-11 17:31:49
您需要检查右子节点的DFS是否找到了该节点。修复：
const left = dfs(node.left, curr);
if (!isFound) {
const right = dfs(node.right, curr);
if(isFound) {
return right;
}
curr.pop();
return; // return nothing, backtracking
}
return left;Stack Overflow用户
发布于 2021-11-11 17:33:56
在数组示例中，您的循环以DFS方式遍历节点，因此每个节点都以这种方式连接。如果我们计算DFS算法中的树节点，3，5，6，2，7实际上是1，2，3，4和5。这样，数组中的整个树应该是这样的:3，5，6，2，7，4，1，0，8。
因此，当您找到目标值时，您将从当前节点弹出，并在DFS算法中将其全部追溯到头节点。
我要么建议找到一种方法来解决这个问题，要么你可以保存这些节点的每个父节点。这意味着您可以使用元组而不是int数组(如果可以接受的话)。索引可能如下所示=(节点值，父值)
(3，空)，(5,3)，(6,5)，(2,5)...
然后相应地追溯..。
https://stackoverflow.com/questions/69932415
复制相似问题
腾讯云开发者
