ruby - 树中最深的路

Question

我有一个包含 n 元素的树，这些元素存储类似 |id|parent_id| 的内容。我需要找到这棵树的最大深度。我需要在 Ruby 中执行此操作，但伪代码也可以帮助我。

Answer 1

假设 {id, parent_id} 对在字典/ map 中，您可以使用 memoization 找到最大深度技术:

主要功能(伪代码):

Map tree; // <<=== This is your tree; id is the key; parent_id is the value
Map depth; // This map is used for memoization
int max = -1;
foreach pair in tree
    max = Max(memoized_depth(id, tree, depth), max)

递归深度函数:

int memoized_depth(id, tree, depth)
    if (depth.containsKey(id)) return depth[id];
    if (!tree.contains(id)) return 0; // no parent means it's a root
    int res = memoized_depth(tree[id] // parent, tree, depth) + 1;
    depth[id] = res;
    return res;