python - 任何人都可以为以下代码提出更好的解决方案，以在 BST 中查找从源节点到目标节点的路径？

Question

class BST:

    def __init__(self, val=None):
        self.left = None
        self.right = None
        self.val = val

    def __str__(self):
        return "[%s, %s, %s]" % (self.left, str(self.val), self.right)

    def insert(self, val):
        if self.isEmpty():
            self.val = val
        elif val < self.val:
            if self.left is None:
                self.left = BST(val)
            else:
                self.left.insert(val)
        else:
            if self.right is None:
                self.right = BST(val)
            else:
                self.right.insert(val)

    def printpath(self,val,path):
        if self.val == val:
            return path
        if self.val > val:
            self.left.printpath(val,path)
        else:
            self.right.printpath(val,path)
        path.append(self.val)


a = BST(4)
a.insert(2)
a.insert(3)
a.insert(5)
a.insert(1)
a.insert(7)
a.insert(6)
a.insert(0)
print a

s = 0
d = 6
lpath = []
rpath = []
lpath.append(s)
a.printpath(s,lpath)
a.printpath(d,rpath)
rpath.reverse()
rpath.append(d)
print lpath,rpath

Answer 1

您所做的是找到从根节点到源节点和目标节点顶部的路径，然后将两者连接起来（以正确的方式，即反转其中一个路径）。

如果树是平衡的（它很可能不会与您的代码一起使用），这将是 O(log n) 并且很难被击败。

我唯一要解决的是你的路径可能不必要地长。例如，以下面的树为例：

    4
   /
  2
 / \
1   3

如果您正在搜索从 1 到 3 的路径，您的代码将返回 1、2、4、4、2、3。此路径实际上可以缩短为 1、2、3。要解决此问题，您可以先计算两者路径的一部分，然后看看它们的末端。虽然末端相同，但缩短两个部分。最后，不要忘记包含最后删除的元素（但只有一次）。

如果您想让代码更快，您可以逐步创建路径的两个部分并在它们相遇时停止。但是这样做会使您的代码更加复杂（它需要使用诸如哈希集之类的东西，或者甚至更好地将深度存储在每个节点中），而这很可能不会显着提高性能。