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

ルート ノードからソース ノードとターゲット ノードの両方のパスを見つけて、両方を連結します (正しい方法で、つまり、パスの 1 つを逆にして)。

ツリーのバランスがとれていれば (これはおそらくあなたのコードには当てはまらないでしょう)、これは O(log n) になり、打ち負かすのは困難です。

私が修正する唯一のことは、パスが不必要に長くなる可能性があることです。たとえば、次のツリーを考えてみます。

    4
   /
  2
 / \
1   3

1 から 3 までのパスを検索していた場合、コードは 1、2、4、4、2、3 を返します。このパスは、実際には 1、2、3 に短縮できます。これを修正するには、最初に両方を計算します。パスの一部を見て、その端を見てください。両端は同じですが、両方の部分を短くします。最後に、最後に削除された要素を含めることを忘れないでください (ただし、一度だけ)。

コードを高速化したい場合は、パスの両方の部分を段階的に作成し、それらが出会ったときに停止することができます。ただし、これを行うと、コードがより複雑になります (ハッシュ セットのようなものを使用するか、各ノードに深さを保存することをお勧めします)。パフォーマンスが大幅に向上する可能性はほとんどありません。