递归更新嵌套对象中指定键及其祖先节点的数值

1. 问题定义与数据结构

在前端开发或数据处理中，我们经常会遇到树形或嵌套的数据结构。假设我们有一个表示分类或层级关系的对象数组，其结构如下：

const data = [
  {
    key: "id1",
    name: "Category 1",
    curr: 0,
    total: 0,
    nodes: [
      {
        key: "id2",
        name: "Applications",
        curr: 20,
        total: 30,
        nodes: [
          {
            key: "id3",
            name: "Gaming",
            curr: 5,
            total: 10,
            nodes: []
          },
          {
            key: "id4",
            name: "Operating System",
            curr: 15,
            total: 20,
            nodes: []
          }
        ]
      }
    ]
  },
  {
    key: "id5",
    name: "Category 2",
    curr: 0,
    total: 0,
    nodes: [
      {
        key: "id6",
        name: "Sub Category",
        curr: 12,
        total: 48,
        nodes: [
          {
            key: "id7",
            name: "Inside Sub",
            curr: 12,
            total: 48,
            nodes: []
          }
        ]
      }
    ]
  },
  {
    key: "id8",
    name: "Last One",
    curr: 0,
    total: 0,
    nodes: []
  }
];

每个对象都包含一个唯一的 key、name、curr（当前值）、total（总值）以及一个 nodes 数组，用于表示其子节点。我们的目标是实现一个函数，当传入一个 key 时，能够找到对应的节点，将其 curr 值递增，并且将此递增操作向上回溯，使其所有祖先节点的 curr 值也相应递增。但需要特别注意的是，最顶层（根级别，即 data 数组中的直接元素，如 id1, id5, id8）的 curr 值不应被修改。

例如，如果调用 incrementRecursively(data, "id4")，预期输出应为：id4 的 curr 从 15 变为 16，其父节点 id2 的 curr 从 20 变为 21。而 id1（根节点）的 curr 保持不变。

2. 常见尝试及局限性

初次尝试解决此类问题时，开发者可能会倾向于使用简单的递归遍历，如下所示：

const incrementRecursively = (nodes, key) => {
  const increment = (currentNodes, targetKey) => {
    currentNodes.forEach((node) => {
      if (node.key === targetKey) {
        node.curr++; // 找到目标，递增
      }
      if (node.nodes && node.nodes.length) {
        // 递归处理子节点
        increment(node.nodes, targetKey);
      }
    });
  };
  increment(nodes, key);
  return nodes;
};

这种方法的问题在于，它只能找到并修改指定 key 的节点。当目标节点被修改后，它不会向其父节点传递任何信息，因此父节点的 curr 值不会被更新。此外，它也没有机制来区分根节点和其他层级的节点，从而无法实现“不修改根节点”的需求。

先见AI

数据为基，先见未见

95

查看详情

3. 递归解决方案：深度追踪与状态传递

为了解决上述问题，我们需要一种机制，让递归函数在子节点发生更新时，能够通知其父节点。同时，我们需要一个参数来追踪当前节点的深度，以便在更新时排除根节点。

3.1 核心思路

1. 状态回传： 递归函数不再仅仅执行操作，而是返回一个布尔值，表示在其当前子树中是否发生了 curr 值的递增。
2. 深度追踪： 引入一个 depth 参数，在每次递归深入时递增。通过判断 depth 的值，我们可以区分根节点（depth = 0）和非根节点（depth > 0）。
3. 条件更新： 只有当 depth > 0 且当前节点或其子节点发生了 curr 值递增时，才递增当前节点的 curr 值。

3.2 示例代码与详细解析

function updateParentChildCurr(nodes, targetKey, depth = 0) {
  // 遍历当前层级的节点
  for (let node of nodes) {
    // 检查当前节点是否是目标节点，或者其子节点中是否找到了目标节点并进行了更新
    // `node.nodes ?? []` 确保即使 node.nodes 为 undefined 或 null 也能安全地进行递归调用
    if (node.key === targetKey || updateParentChildCurr(node.nodes ?? [], targetKey, depth + 1)) {
      // 如果满足上述条件（即当前节点或其子节点发生了更新）
      // 并且当前节点不是根节点（depth > 0）
      if (depth > 0) {
        node.curr++; // 递增当前节点的 curr 值
      }
      // 返回 true，向上层级通知：该路径上发生了更新
      return true;
    }
  }
  // 如果遍历完当前层级的所有节点，都没有找到目标或子节点未更新，则返回 false
  return false;
}

// 示例调用
console.log("原始数据:", JSON.stringify(data, null, 2));

// 调用函数，更新 key 为 "id4" 的节点及其父节点
updateParentChildCurr(data, 'id4');
console.log("\n更新 'id4' 后的数据:", JSON.stringify(data, null, 2));

// 再次调用，更新 key 为 "id7" 的节点及其父节点
updateParentChildCurr(data, 'id7');
console.log("\n更新 'id7' 后的数据:", JSON.stringify(data, null, 2));

代码解析：

1. function updateParentChildCurr(nodes, targetKey, depth = 0):
   • nodes: 当前函数调用处理的节点数组。
   • targetKey: 我们要查找并更新的节点的 key。
   • depth = 0: 默认参数，表示当前处理的节点数组的深度。顶层 data 数组的深度为 0。每当递归深入一层，depth 就会加 1。
2. for (let node of nodes): 迭代当前 nodes 数组中的每一个节点。
3. if (node.key === targetKey || updateParentChildCurr(node.nodes ?? [], targetKey, depth + 1)): 这是核心逻辑所在。
   • node.key === targetKey: 检查当前节点是否就是我们要找的目标节点。如果是，说明我们已经找到了要递增的节点。
   • updateParentChildCurr(node.nodes ?? [], targetKey, depth + 1): 如果当前节点不是目标，则递归调用自身，处理当前节点的子节点。
     • node.nodes ?? []: 使用空值合并运算符 (??)，确保如果 node.nodes 是 null 或 undefined，也能安全地传递一个空数组，避免运行时错误。
     • depth + 1: 递增深度，表示我们进入了下一层。
   • || 运算符：这个逻辑非常关键。如果 node.key === targetKey 为 true（当前节点是目标），或者递归调用 updateParentChildCurr 返回 true（表示在当前节点的某个子孙节点中找到了目标并进行了更新），那么整个 if 条件就为 true。这意味着在当前 node 的路径上，要么是 node 本身，要么是其子孙节点发生了 curr 值递增。
4. if (depth > 0): 如果 if 条件为 true，我们知道当前路径上发生了更新。此时，我们检查 depth。只有当 depth 大于 0 时（即当前节点不是根节点），才执行 node.curr++。这完美地满足了“不修改根节点”的要求。
5. return true: 当 if 条件满足（即找到了目标并/或更新了父节点）时，函数立即返回 true。这个 true 值会向上层调用者传递，告知其父节点也需要考虑更新自己的 curr 值。
6. return false: 如果 for 循环结束，没有找到 targetKey 对应的节点，也没有在其任何子孙节点中找到，那么函数返回 false，表示当前路径上没有发生更新。

4. 注意事项

• 原地修改 (In-place Modification): 上述解决方案直接修改了原始 data 数组。在许多应用场景中，这可能是可以接受的。但如果需要保持数据的不可变性（例如在 React/Redux 应用中），则需要在每次修改时创建新的对象和数组副本。这会使代码更复杂，但能避免副作用。
• depth 参数的重要性: depth 参数是实现层级控制的关键。通过它，我们可以精确地决定哪些层级的节点应该被修改，哪些不应该。
• key 的唯一性: 该解决方案假设 key 在整个树形结构中是唯一的。如果 key 不唯一，则可能会更新多个匹配的节点及其祖先。
• 鲁棒性: node.nodes ?? [] 的用法增强了代码的鲁棒性，能够处理 nodes 属性可能缺失或为 null/undefined 的情况，避免了潜在的 TypeError。

5. 总结

通过结合递归遍历、深度追踪参数以及利用函数返回值作为状态传递机制，我们成功地实现了一个高效且准确的解决方案，用于在嵌套对象数组中根据指定键递归更新目标节点及其所有父节点的特定数值，同时遵守了不修改根节点的特定业务规则。这种模式在处理树形数据结构时非常有用，可以灵活应用于各种复杂的层级数据操作场景。

以上就是递归更新嵌套对象中指定键及其祖先节点的数值的详细内容，更多请关注php中文网其它相关文章！