java - 遍历树形结构的算法

Class Diagnostic {

//Get the size in bytes of an object
static long sizeOf(Object object);

//Get the references for an object (leafs)
static List<Object> getRefs(Object object);

//Implement this with those above
public Long objectSize(Object object);
}

您将如何实现objectSize以返回对象的字节大小？

方法objectSize返回组合的所有子节点(树中的每个节点)的大小(以字节为单位)。

示例:

               Object A (19 bytes)
                      /    \
                     /      \
                   B(20)    C(37)
                   /
                  /
                C(15)

答案:19 + 20 + 37 + 15 = 91

我在面试中遇到了这个问题，我很好奇看到其他答案。从那以后，我对树遍历算法并不了解。

我想出了这个...(我知道这是好不好；)，只是想学习)

    public Long objectSize(Object object) {
    List<Object> objectList = new ArrayList<Object>();

    Long sum = sizeOf(object);
    objectList = getRefs(object);

    for(Object object : objectList){
           sum += objectSize(object);
    }

return sum;
}

我注意到我可能有一个循环并经历了stackoverflow错误，因为我没有检查是否已经通过“节点”。然后，我很艰难地应该拥有另一个数据结构(例如用于处理键/值的哈希图)来处理用于比较的临时列表。

最佳答案

如果要处理真正的“树”结构，则不必担心周期。

您已经有了基本的想法，但是您需要考虑递归调用的实际返回值。如果我们假设对象的总大小(objectSize())等于其子项的大小加上其自身大小(sizeOf())的总和，那么您只需要确保将所有子树的大小加在一起即可。

这是您可以做到的一种方法:

public Long objectSize(Object object) {
    List<Object> objectList = getRefs(object);
    long sum = sizeOf(object);

    for(Object object : objectList) {
         sum += objectSize(object);
    }

    return Long.valueOf(sum);
}

您缺少的是，递归objectSize调用返回了一个值，并且该值需要包含(在本例中为加法)到您的返回值中。