1

所以我试图在python中使用Euler tour和RMQ和稀疏表来实现LCA。如果我从树的左侧插入数字，我的代码工作正常。构建树的代码是：

节点类有数据，left_child 和 right_child：

class Node:
    def __init__(self, value):
        self.data = value
        self.right_child = None
        self.left_child = None

然后我有一个用于构建树的树类：

class Tree:
    content = []
    
    def __init__(self):
        self.root = None
        
    def add_child(self, arr, root, i, n):
        if i < n:
            temp = Node(arr[i])
            root = temp
            
            root.left_child = self.add_child(arr, root.left_child, 2 * i + 1, n)
            root.right_child = self.add_child(arr, root.right_child, 2 * i + 2, n)
            
        return root
    
    def pre_order(self, root):
        
        if root != None:
            Tree.content.append(root.data)
            self.pre_order(root.left_child)
            self.pre_order(root.right_child)
            
        return Tree.content

最后，我得到了一个 LCA 类，它主要包含构建稀疏表的函数，然后在稀疏表上执行 RMQ，然后是执行欧拉遍历部分的函数，最后是查找 LCA 的函数。

class LCA:
    
    def __init__(self, root, length):
        self.pre_process_array = [[0] * (math.floor(math.log2(length) + 2)) for _ in range((length * 2) - 1)]
        self.euler = [0] * (length * 2 - 1)
        self.height = [0] * (length * 2 - 1)
        self.index = [-1  for _ in range(length + 1)]
        self.tour = 0
        
        self.euler_tour(root, 0)
        self.build_sparse_table(self.height)
        
        print(self.pre_process_array)
        
    def build_sparse_table(self, height_array):
        for i in range(len(height_array)):
            self.pre_process_array[i][0] = height_array[i]
            
        j = 1
        
        while (1 << j) <= len(height_array):
            
            i = 0
            while (i + (1 << j) - 1) < len(height_array):
                
                if self.pre_process_array[i][j - 1] < self.pre_process_array[i + (1 << (j - 1))][j-1]:
                    self.pre_process_array[i][j] = self.pre_process_array[i][j - 1]
                else:
                    self.pre_process_array[i][j] = self.pre_process_array[i + (1 << (j - 1))][j - 1]
                    
                i += 1
            
            j += 1
            
    def rmq(self, l, h):
        j = int(math.log2(h - l + 1))
        
        if self.pre_process_array[l][j] <= self.pre_process_array[h - (1 << j) + 1][j]:
            return self.pre_process_array[l][j]
        else:
            return self.pre_process_array[h - (1 << j) + 1][j]
        
    def euler_tour(self, root, level):
        if root is not None:

            self.euler[self.tour] = root.data
            self.height[self.tour] = level
            self.tour += 1
            
            if self.index[root.data] == -1:
                self.index[root.data] = self.tour - 1
                
            if root.left_child is not None:
                self.euler_tour(root.left_child, level + 1)
                self.euler[self.tour] = root.data
                self.height[self.tour] = level
                self.tour += 1
                
            if root.right_child is not None:
                self.euler_tour(root.right_child, level + 1)
                self.euler[self.tour] = root.data
                self.height[self.tour] = level
                self.tour += 1
            
    def find_LCA(self, val1, val2):
        if val1 >= len(self.index) or val2 >= len(self.index) or self.index[val1] == -1 or self.index[val2] == -1:
            return -1
        
        if self.index[val1] > self.index[val2]:
            return self.euler[self.rmq(self.index[val2], self.index[val1])]
        elif self.index[val2] > self.index[val1]:
            return self.euler[self.rmq(self.index[val1], self.index[val2])]

我的驱动程序代码如下：

tree_data = [1,2,3,4,5,6,7,8,9]
length = len(tree_data)
         
tree = Tree()
root = tree.root

tree.root = tree.add_child(tree_data, root, 0, length)
l = LCA(tree.root, length)

print(l.find_LCA(6, 3))

所以，我的树应该是这样的：

                               1
                             /   \
                            2     3
                           / \   / \
                          4   5  6  7
                         / \
                        8   9

现在，如果我尝试找到 LCA(8, 9) 或 LCA(4, 3)，我会得到正确的输出，但每当我尝试给出 LCA(6, 7) 或 LCA(3, 7) 时，它总是保持返回 2 作为应该分别返回 3 和 3 的答案。

我不知道错误在哪里，从我的角度来看，它看起来还不错。

4

0 回答 0