如何求一個二叉排序樹兩個節(jié)點的公共祖先？搜索二叉樹的特點：任意一個節(jié)點的左子樹中所有節(jié)點的值都小于該節(jié)點的值，右子樹中所有節(jié)點的值都大于該節(jié)點的值。要解決此問題：從樹的根節(jié)點開始，比較兩個節(jié)點。如果當

如何求一個二叉排序樹兩個節(jié)點的公共祖先？

搜索二叉樹的特點：任意一個節(jié)點的左子樹中所有節(jié)點的值都小于該節(jié)點的值，右子樹中所有節(jié)點的值都大于該節(jié)點的值。

要解決此問題：

從樹的根節(jié)點開始，比較兩個節(jié)點。如果當前節(jié)點的值大于兩個節(jié)點的值，則兩個節(jié)點最近的共同祖先節(jié)點必須在該節(jié)點的左子樹中，則下一步是遍歷當前節(jié)點的左子樹；

如果當前節(jié)點的值小于兩個節(jié)點的值，則最近的共同祖先節(jié)點兩個節(jié)點的節(jié)點必須在節(jié)點的左子樹中祖先節(jié)點必須在節(jié)點的右子樹中。下一步是遍歷當前節(jié)點的右子樹，直到發(fā)現(xiàn)第一個值為2

您可能有一個思維慣性，即在visit（）中獲得的序列就是路徑。事實上，正確的想法是觀察堆棧中的序列。當遍歷二叉樹時，使用堆棧。當使用post順序遍歷到目標節(jié)點n時，堆棧中的序列是n節(jié)點的所有父節(jié)點（堆棧是一個數(shù)組）。可以按以下順序繪制一棵二叉樹來遍歷它。注意堆棧中的元素，而不是visit（）元素

在二叉樹中有兩個結(jié)點m和n,如果m是n的祖先,可以找到從m到n的路徑的遍歷方式是？

如果二叉樹是Trident鏈表存儲或順序存儲，您可以通過從兩個節(jié)點到根節(jié)點快速找到它。如果是二進制鏈表存儲，可以使用非遞歸順序遍歷。分別遍歷兩個節(jié)點時，比較當時棧中的情況