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

如何求一個(gè)二叉排序樹(shù)兩個(gè)節(jié)點(diǎn)的公共祖先？

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

要解決此問(wèn)題：

從樹(shù)的根節(jié)點(diǎn)開(kāi)始，比較兩個(gè)節(jié)點(diǎn)。如果當(dāng)前節(jié)點(diǎn)的值大于兩個(gè)節(jié)點(diǎn)的值，則兩個(gè)節(jié)點(diǎn)最近的共同祖先節(jié)點(diǎn)必須在該節(jié)點(diǎn)的左子樹(shù)中，則下一步是遍歷當(dāng)前節(jié)點(diǎn)的左子樹(shù)；

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

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

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

如果二叉樹(shù)是Trident鏈表存儲(chǔ)或順序存儲(chǔ)，您可以通過(guò)從兩個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)快速找到它。如果是二進(jìn)制鏈表存儲(chǔ)，可以使用非遞歸順序遍歷。分別遍歷兩個(gè)節(jié)點(diǎn)時(shí)，比較當(dāng)時(shí)棧中的情況