js终止递归

终止递归

1. 实现目标：js 编写递归方法查找指定节点；

2. 需解决问题：找到所需节点后，递归不会终止，直到所有节点遍历完成后才会停止，会消耗性能

3. 解决方案：优化递归方法，在找到所需节点后，直接终止递归

4. 代码：

// 假设我们有一个简单的树节点结构
function TreeNode(value, children = []) {
  this.value = value;
  this.children = children;
}

// 创建示例树
const root = new TreeNode(1, [
  new TreeNode(2, [new TreeNode(4), new TreeNode(5)]),
  new TreeNode(3, [
    new TreeNode(6),
    new TreeNode(7, [new TreeNode(8), new TreeNode(9)]),
  ]),
]);
// 错误写法（该写法虽然能找到正确节点，但找到正确节点后还是会遍历后续节点，对于某些"洁癖患者"来说不能容忍，而且需要定义外部变量不够优雅）
let result = null;
// 递归遍历树的函数
function traverseTreeErr(findVal, node = root) {
  console.log("traverseTreeErr", node); // 打印这里就可以知道 找到对应节点后，会继续遍历子节点
  // 检查当前节点的值是否匹配
  if (node.value === findVal) {
    result = node;
    return;
  }

  // 遍历子节点
  for (let child of node.children) {
    traverseTreeErr(findVal, child); // 递归调用
  }
}
traverseTreeErr(6);
console.log("traverseTreeErr.result", result);
// 正确写法（该写法 不需要定义外部变量且找到所需节点后立即终止了递归）
// 递归遍历树的函数
function traverseTree(findVal, node = root) {
  console.log("traverseTree", node);
  // 检查当前节点的值是否匹配
  if (node.value === findVal) {
    return node;
  }

  // 遍历子节点
  for (let child of node.children) {
    let result = traverseTree(findVal, child); // 递归调用
    if (result) {
      // 如果找到了匹配的节点，返回它
      return result;
    }
  }
  // 如果没有找到匹配的节点，返回null
  return null;
}
// 调用traverseTree来查找值为3的节点
console.log("traverseTree.result", traverseTree(6)); // 应该输出值为6的TreeNode对象