如何在JS/TS树形结构中查找节点及其搜索路径

Your current stack-based search function does a great job locating the target node, but to capture the path from the root to that node, we need to adjust our approach to track the traversal path as we go. Let's cover two solid solutions: an improved stack-based implementation and a recursive approach.

Stack-Based Solution (Modified) #

Instead of just storing nodes in the stack, we'll store objects that contain both the current node and the path taken to reach it. This way, when we find our target node, we already have the full path ready.

Here's the updated code:

const treeData = { id: 1, name: "Node 1", child: [{ id: 2, name: "Node 2", child: [{ id: 3, name: "Node 3" }, { id: 4, name: "Node 4", child: [{ id: 10, name: "Node 10" }] } ] }, { id: 5, name: "Node 5", child: [{ id: 6, name: "Node 6" }] } ] };

function searchTreeWithPath(nodeId, root) {
  // Each stack item is { node: currentNode, path: arrayOfNodesToHere }
  const stack = [{ node: root, path: [root] }];
  
  while (stack.length > 0) {
    const { node, path } = stack.pop();
    
    // Check if this is our target node
    if (node.id === nodeId) {
      return {
        foundNode: node,
        path: path.map(n => ({ id: n.id, name: n.name })) // Optional: return just id/name for cleaner path
      };
    }
    
    // Push children to stack (reverse to maintain order, optional)
    if (node.child) {
      // Reverse so we process children in original order (since stack is LIFO)
      [...node.child].reverse().forEach(child => {
        stack.push({
          node: child,
          path: [...path, child]
        });
      });
    }
  }
  
  // If node not found
  return { foundNode: null, path: [] };
}

// Test it
const result = searchTreeWithPath(10, treeData);
console.log("Found node:", result.foundNode);
console.log("Path to node:", result.path);

Notes: #

• We reverse the children before pushing to the stack to keep the traversal order consistent with your original function (since stacks are last-in-first-out). If order doesn't matter, you can skip the reverse.
• The path is returned as an array of node objects (or just id/name if you use the mapped version), showing the full route from root to target.

Recursive Solution #

Recursion can make path tracking feel more intuitive, as we can pass the current path along with each recursive call. If a child returns a valid path, we prepend the current node to it; if not, we keep searching.

Here's the recursive version:

function recursiveSearchWithPath(nodeId, currentNode, currentPath = [currentNode]) {
  // Check if current node is the target
  if (currentNode.id === nodeId) {
    return {
      foundNode: currentNode,
      path: currentPath.map(n => ({ id: n.id, name: n.name }))
    };
  }
  
  // If no children, return null
  if (!currentNode.child) {
    return null;
  }
  
  // Recurse through each child
  for (const child of currentNode.child) {
    const result = recursiveSearchWithPath(nodeId, child, [...currentPath, child]);
    if (result) {
      return result;
    }
  }
  
  // Node not found in this branch
  return null;
}

// Test it
const recursiveResult = recursiveSearchWithPath(10, treeData);
console.log("Recursive found node:", recursiveResult?.foundNode);
console.log("Recursive path:", recursiveResult?.path);

Notes: #

• We use a default parameter for currentPath to start with the root node.
• As soon as we find the target node in any child branch, we return the result immediately to avoid unnecessary recursion.

Both solutions will give you the full path from the root to your target node. Pick the one that fits better with your codebase—stack-based is better for very deep trees (to avoid stack overflow), while recursive is more readable for most cases.

内容的提问来源于stack exchange，提问作者Code Guru