如何找到给定id的路径?
How to find a path of a given id?
我有一棵树:
type Tree = {
id: string;
pathToNode?: string[];
children: Tree[];
};
export const treeData: Tree = {
id: '1',
children: [
{
id: '2',
children: [
{ id: '3', children: [] },
{ id: '4', children: [] },
],
},
{ id: '5', children: [] },
],
};
我希望找到 id 的路径和 return 该路径(或者换句话说,该节点的父节点)。
这是我拥有的(但它不起作用):
const findPath = (tree: Tree, id: string, pathStack: string[]) => {
if (tree.id === id) {
tree.pathToNode = pathStack;
return { id: tree.id, path: tree.pathToNode };
}
pathStack.push(tree.id);
if (tree.children.length) {
tree.children.map((node) => findPath(node, id, pathStack));
}
return { id: tree.id, path: pathStack };
};
如果我调用 findPath 并传入 id:'2',我应该得到:
const pathStack:string[] = [];
const result = findPath(treeData, '2', pathStack);
// result should equal: {id: '2', pathToNode: ['1']}
如果我调用 findPath 并传入 id:'4',我应该得到:
const pathStack:string[] = [];
const result = findPath(treeData, '4', pathStack);
// result should equal: {id: '4', pathToNode: ['1', '2']}
如果我调用 findPath 并传入 id:'5',我应该得到:
const pathStack:string[] = [];
const result = findPath(treeData, '5', pathStack);
// result should equal: {id: '5', pathToNode: ['1']}
如果我传入“1”的根 ID,响应将是 {'1', pathToNode: []}
您需要为 children 提早 return 并尊重 return 价值。
const
treeData = { id: '1', children: [{ id: '2', children: [{ id: '3', children: [] }, { id: '4', children: [] }] }, { id: '5', children: [] }] },
findPath = (tree, id, pathStack = []) => {
if (tree.id === id) return { id: tree.id, path: pathStack };
pathStack.push(tree.id);
for (const node of tree.children) {
const result = findPath(node, id, [...pathStack]);
if (result) return result;
}
};
console.log(findPath(treeData, '4'));
console.log(findPath(treeData, '5'));
你的逻辑看起来不错,只需要更正几处
我在您的代码中添加了一些您需要更正的注释
const findPath = (tree: Tree, id: string, pathStack: string[]) => {
if (tree.id === id) {
tree.pathToNode = pathStack; // no need to add pathstack to tree
return { id: tree.id, path: tree.pathToNode }; // use pathStack instead of tree.pathToNode
}
pathStack.push(tree.id);
if (tree.children.length) {
tree.children.map((node) => findPath(node, id, pathStack)); // this will loops to all your childs even if you find the result node
//So use for loop and break the loop when you find the result node
}
return { id: tree.id, path: pathStack };
};
我的密码是
const findPath = (tree: Tree, id: string, pathStack: string[]) => {
if (tree.id === id)
return { id: tree.id, path: pathStack };
pathStack.push(tree.id);
for (const node of tree.children) {
const result = findPath(node, id, [...pathStack]);
if (result) return result; //this will stop going deeper or to unwanted childs after getting the result
}
};
正如评论中讨论的那样,查找数组中某些节点的路径。
let foundPaths = [];
let path
arr.map(element => {
path = findPath(tree, element.id);
if(path) {foundPaths.push(path)}
})
我有一棵树:
type Tree = {
id: string;
pathToNode?: string[];
children: Tree[];
};
export const treeData: Tree = {
id: '1',
children: [
{
id: '2',
children: [
{ id: '3', children: [] },
{ id: '4', children: [] },
],
},
{ id: '5', children: [] },
],
};
我希望找到 id 的路径和 return 该路径(或者换句话说,该节点的父节点)。
这是我拥有的(但它不起作用):
const findPath = (tree: Tree, id: string, pathStack: string[]) => {
if (tree.id === id) {
tree.pathToNode = pathStack;
return { id: tree.id, path: tree.pathToNode };
}
pathStack.push(tree.id);
if (tree.children.length) {
tree.children.map((node) => findPath(node, id, pathStack));
}
return { id: tree.id, path: pathStack };
};
如果我调用 findPath 并传入 id:'2',我应该得到:
const pathStack:string[] = [];
const result = findPath(treeData, '2', pathStack);
// result should equal: {id: '2', pathToNode: ['1']}
如果我调用 findPath 并传入 id:'4',我应该得到:
const pathStack:string[] = [];
const result = findPath(treeData, '4', pathStack);
// result should equal: {id: '4', pathToNode: ['1', '2']}
如果我调用 findPath 并传入 id:'5',我应该得到:
const pathStack:string[] = [];
const result = findPath(treeData, '5', pathStack);
// result should equal: {id: '5', pathToNode: ['1']}
如果我传入“1”的根 ID,响应将是 {'1', pathToNode: []}
您需要为 children 提早 return 并尊重 return 价值。
const
treeData = { id: '1', children: [{ id: '2', children: [{ id: '3', children: [] }, { id: '4', children: [] }] }, { id: '5', children: [] }] },
findPath = (tree, id, pathStack = []) => {
if (tree.id === id) return { id: tree.id, path: pathStack };
pathStack.push(tree.id);
for (const node of tree.children) {
const result = findPath(node, id, [...pathStack]);
if (result) return result;
}
};
console.log(findPath(treeData, '4'));
console.log(findPath(treeData, '5'));
你的逻辑看起来不错,只需要更正几处 我在您的代码中添加了一些您需要更正的注释
const findPath = (tree: Tree, id: string, pathStack: string[]) => {
if (tree.id === id) {
tree.pathToNode = pathStack; // no need to add pathstack to tree
return { id: tree.id, path: tree.pathToNode }; // use pathStack instead of tree.pathToNode
}
pathStack.push(tree.id);
if (tree.children.length) {
tree.children.map((node) => findPath(node, id, pathStack)); // this will loops to all your childs even if you find the result node
//So use for loop and break the loop when you find the result node
}
return { id: tree.id, path: pathStack };
};
我的密码是
const findPath = (tree: Tree, id: string, pathStack: string[]) => {
if (tree.id === id)
return { id: tree.id, path: pathStack };
pathStack.push(tree.id);
for (const node of tree.children) {
const result = findPath(node, id, [...pathStack]);
if (result) return result; //this will stop going deeper or to unwanted childs after getting the result
}
};
正如评论中讨论的那样,查找数组中某些节点的路径。
let foundPaths = [];
let path
arr.map(element => {
path = findPath(tree, element.id);
if(path) {foundPaths.push(path)}
})