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