求BST中兩個(gè)節(jié)點(diǎn)的公共父節(jié)點(diǎn)
BST 二叉搜索樹(shù) 特點(diǎn): 每個(gè)節(jié)點(diǎn)的左子樹(shù)都小于它 右子樹(shù)都大于它
思路:
基本思想是：給定二叉樹(shù)中的兩個(gè)節(jié)點(diǎn)n1, n2(假定n1<n2), 其最近的公共祖先節(jié)點(diǎn)的值n應(yīng)該滿足 n1<n<n2，所以我們可以前序遍歷二叉搜索樹(shù)，當(dāng)發(fā)現(xiàn)一個(gè)節(jié)點(diǎn)的值在n1和n2之間時(shí)，則此節(jié)點(diǎn)為所求節(jié)點(diǎn)。如果節(jié)點(diǎn)的值大于n1和n2，則所求節(jié)點(diǎn)在當(dāng)前節(jié)點(diǎn)的左子樹(shù)；否則在右子樹(shù)。（算法很簡(jiǎn)單，對(duì)于樹(shù)的求解關(guān)鍵是用好先中后序遍歷，再難也不過(guò)如此，呵呵）