以迭代的方式查找对象的深度

Question

我正在编写一个计算物体深度的函数.

这是我的递归版本,似乎按预期工作:

function findDepth(obj, firstCall = true) {
  if (firstCall && typeof obj !== "object") {
    return -1;
  }
  return Object.keys(obj).reduce((max, k) => {
    if (typeof obj[k] === "object" && obj[k] !== null) {
      const val = findDepth(obj[k], false) + 1;
      if (val > max) {
        max = val;
      }
    }
    return max;
  }, 1);
}

const input1 = {
  a: {
    b: "test",
    c: {
      d: {
        e: {
          f: [1, 2, 3],
          g: {
            a: null,
            z: {
              d: "casdsadasdsa",
              q: {
                z: {
                  i: undefined
                }
              }
            }
          }
        }
      },
      c: {
        a: "sad"
      }
    },
    d: {
      e: 5
    }
  },
  b: {
    c: {
      d: "dsada"
    }
  }
};

const input2 = {
  w: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk",
        q: {
          w: {
            z: "dsajkdasjdla"
          }
        }
      },
      h: "dsiaodsiad"
    }
  },
  a: "test",
  b: "test2",
  c: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk"
      },
      h: "dsiaodsiad"
    }
  },
  e: "bye"
};

console.log(findDepth(input1));
console.log(findDepth(input2));

现在我正在尝试编写迭代版本,但我找不到使循环工作的最佳方法.

function findDepthIterative(obj) {
  if (typeof obj !== "object") {
    return -1;
  }
  let max = 1;
  let copy = Object.assign({}, obj);
  let keys = Object.keys(copy);
  while (keys.length) {
    if (typeof copy[keys[0]] !== "object" && copy[keys[0]] !== null) {
      delete copy[keys[0]];
      keys = Object.keys(copy);
    } else {
      max++;
      copy = Object.assign({}, copy[keys[0]]);
      keys = Object.keys(copy);
    }
  }
  return max;
}

const input1 = {
  a: {
    b: "test",
    c: {
      d: {
        e: {
          f: [1, 2, 3],
          g: {
            a: null,
            z: {
              d: "casdsadasdsa",
              q: {
                z: {
                  i: undefined
                }
              }
            }
          }
        }
      },
      c: {
        a: "sad"
      }
    },
    d: {
      e: 5
    }
  },
  b: {
    c: {
      d: "dsada"
    }
  }
};

const input2 = {
  w: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk",
        q: {
          w: {
            z: "dsajkdasjdla"
          }
        }
      },
      h: "dsiaodsiad"
    }
  },
  a: "test",
  b: "test2",
  c: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk"
      },
      h: "dsiaodsiad"
    }
  },
  e: "bye"
};

console.log(findDepthIterative(input1));
console.log(findDepthIterative(input2));

从输出和代码中可以看出,它只需要循环内的第一个属性:

while (keys.length) {
    if (typeof copy[keys[0]] !== "object" && copy[keys[0]] !== null) {
      delete copy[keys[0]];
      keys = Object.keys(copy);
    } else {
      max++;
      copy = Object.assign({}, copy[keys[0]]);
      keys = Object.keys(copy);
    }
  }

我的想法是每次迭代删除属性,但我没有以正确的方式.我试图改变它,copy[keys[keys.length - 1]]但这样只需要最后一个属性.实际上问题是如何在所有深度级别上循环所有键,就像在递归版本中一样.

有关如何以迭代方式实现此算法的任何建议？

甚至关于如何改进递归的(或者如果我遗漏了某些东西)的任何建议都非常受欢迎.

ps NO LOADASH,UNDERSCORE,RAMDA等等.Just Vanilla JS

Answer 1

您只需要保持堆叠并将孩子推入其中,同时跟踪当前深度.您可以通过将一个数组推[depth, obj]入堆栈然后pop()在推送子项之前将一个添加到深度来跟踪它.

const input1  = {w: {d: "hello",f: {g: "dsadas",z: {b: "dsajkdasjldk",q: {w: {z: "dsajkdasjdla"}}},h: "dsiaodsiad"}},a: "test",b: "test2",c: {d: "hello",f: {g: "dsadas",z: {b: "dsajkdasjldk"},h: "dsiaodsiad"}},e: "bye"};
  
  
function findDepthIterative(obj) {
    if (typeof obj !== "object") {
      return -1;
    }
    let max = 0;
    // current depth, children
    let stack = [[0, Object.values(obj)]];
    
    while(stack.length){
        let [depth, cur] = stack.pop()
        if (depth > max) max = depth

        if (typeof cur === "object" && cur !== null){
            Object.values(cur).forEach(c => stack.push([depth+1, c]))     
        }
    }
    return max
  }
  

console.log(findDepthIterative(input1))

// sanity check:
const depth0 = {}
const depth1 = {a:1}
const depth2 = {a:{b:2}}

console.log(findDepthIterative(depth0))
console.log(findDepthIterative(depth1))
console.log(findDepthIterative(depth2))