如何求一個(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ù)，直到找到第一個(gè)值為2為止

二叉排序樹(shù)也稱(chēng)為二叉搜索樹(shù)

算法步驟：[S1:如果樹(shù)為空（第一個(gè)元素到達(dá)），根節(jié)點(diǎn)用該元素建立

S2:二進(jìn)制搜索到葉節(jié)點(diǎn)

S2.1:如果葉節(jié)點(diǎn)關(guān)鍵字大于待插入節(jié)點(diǎn)關(guān)鍵字，則將待插入節(jié)點(diǎn)的關(guān)鍵字設(shè)為其左子項(xiàng)

否則，成為它的右子級(jí)

S3:重復(fù)步驟S2，直到所有節(jié)點(diǎn)都被插入

時(shí)間復(fù)雜度：通過(guò)二進(jìn)制搜索找到要插入位置的每個(gè)節(jié)點(diǎn)的復(fù)雜度為O（LGN），因此總復(fù)雜度為O（nlgn）]//希望對(duì)您有用