如何求一個二叉排序樹兩個節(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é)點的右子樹，直到找到第一個值為2為止

二叉排序樹也稱為二叉搜索樹

算法步驟：[S1:如果樹為空（第一個元素到達），根節(jié)點用該元素建立

S2:二進制搜索到葉節(jié)點

S2.1:如果葉節(jié)點關鍵字大于待插入節(jié)點關鍵字，則將待插入節(jié)點的關鍵字設為其左子項

否則，成為它的右子級

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

時間復雜度：通過二進制搜索找到要插入位置的每個節(jié)點的復雜度為O（LGN），因此總復雜度為O（nlgn）]//希望對您有用