计算树的高度 - Java

Question

我目前有一种计算树高的方法，但我需要加快算法速度，以便运行不到 6 秒。我正在考虑实现一些递归的东西，但不确定如何去做。

public class TreeHeight {
    int n;
    int parent[];

    void read() throws IOException {
        FastScanner in = new FastScanner();
        n = in.nextInt();
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = in.nextInt();
        }
    }

    int computeHeight() {
                    // Replace this code with a faster implementation
        int maxHeight = 0;
        for (int vertex = 0; vertex < n; vertex++) {
            int height = 0;
            for (int i = vertex; i != -1; i = parent[i])
                height++;
            maxHeight = Math.max(maxHeight, height);// assign the max of the two arguements
        }
        return maxHeight;
    }
}

Answer 1

递归解决方案可能看起来像这样，具体取决于如何您在内部存储树。此解决方案假定您有一个 class 节点，该节点具有指向其所有节点子节点的链接。

代码的作用是从根开始递归计算树中每条向下路径的高度（或实际深度），并选择最长的路径。

int computeHeight(Node root){
    int levels = 0;
    for(Node child : root.children){
        int childHeight = computeHeight(child);
        if(childHeight > levels){
            levels = childHeight;
        }
    }
    return levels + 1;
}

Answer 2

您可以使用记忆改进您的算法。我使用数组 heights 来存储已经计算出的结果。每当计算出一个结果时，它就存储在数组中，不再计算。这可以使您的算法对于大型数组的速度显着加快。

int computeHeight() {
    int maxHeight = 0;
    int[] heights = new int[parent.length];
    for (int vertex = 0; vertex < n; vertex++) {
        if (heights[vertex] != 0)       // We've been here before
            continue;
        int height = 0;
        for (int i = vertex; i != -1; i = parent[i]) {
            if (heights[i] != 0) {     // We've been here before 
                height += heights[i];   
                break;
            }
            height++;
        }
        maxHeight = Math.max(maxHeight, height);
        // Now we store the results in the array to save us time in the future.
        for (int i = vertex; i != -1; i = parent[i]) {
            if (heights[i] != 0)
                break;
            heights[i] = height--;
        }
    }
    return maxHeight;
}

Answer 3

如果你有逻辑思考

一棵树的高度=max(左子树的高度,右子树的高度)+1

所以递归的方法是递归计算左右子树的高度和return max+1。

这是函数的样子

int Height(Node root)
{

    if(root==null)
     return 0;

 int l=Height(root.left);
 int r=Height(root.right);

return max(l,r)+1;
}

看看这个递归解决方案是否适合你。

Answer 4

对于需要比@Paul Boddington 提到的算法更快算法的任何人来说，只是一个跟进comment/note。

(一位朋友用上面的算法做了一个class作业，发现速度不够快，过不了时限)

不需要每次都遍历到根节点，只要在第一个已经计算好的节点处停下即可。

所以最重要的区别是两行：

            while self.heights[i] == 0 and i != -1:

替换上面的算法：

        for (int i = vertex; i != -1; i = parent[i]) {

样本Python代码：

class TreeHeight:
def read(self):
    self.parent = []  // input parent array
    self.n = len(self.parent)
    self.heights = [0] * self.n

def get_root(self):
    return self.parent.index(-1)

def compute_height(self):
    # Replace this code with a faster implementation

    maxHeight = 0
    for vertex in range(self.n):
        if self.heights[vertex] != 0:
            continue

        if self.parent[vertex] == -1:
            self.heights[vertex] = 1

        height = 0
        i = vertex
        while self.heights[i] == 0 and i != -1:
            height += 1
            i = self.parent[i]
        height += self.heights[i]

        maxHeight = max(maxHeight, height)

        i = vertex
        while self.heights[i] == 0 and i != -1:
                  self.heights[i] = height
                  height = height - 1
                  i = self.parent[i]

        print vertex, self.heights[vertex]
        print "maxHeight", maxHeight

    return maxHeight

计算树的高度 - Java

Computing the height of a tree - Java

java

algorithm

tree

recursion

data-structures

样本Python代码：