參考文章： http://blog.csdn.net/bh_xiaoxinba/article/details/53030043
題目
給定一顆二叉樹(shù)的頭結(jié)點(diǎn)，和這顆二叉樹(shù)中2個(gè)節(jié)點(diǎn)n1和n2倘要，求這兩個(gè)節(jié)點(diǎn)的最近公共祖先厅克；
思路
利用后序遍歷實(shí)現(xiàn)艰躺；
對(duì)于當(dāng)前節(jié)點(diǎn)cur譬嚣，如果節(jié)點(diǎn)為null或者等于n1或n2中的一個(gè)懈贺，則直接返回cur搬男；
先處理左右子樹(shù)拣展，左子樹(shù)返回left，右子樹(shù)返回right缔逛；判斷l(xiāng)eft和right备埃；
1）left和right均為null，說(shuō)明以cur為根的樹(shù)上沒(méi)發(fā)現(xiàn)n1和n2褐奴；
2）left和right均不為null按脚，說(shuō)明在左子樹(shù)上發(fā)現(xiàn)了n1或n2，在右子樹(shù)上也發(fā)現(xiàn)了n1或n2敦冬，cur為n1和n2的首次相遇節(jié)點(diǎn)辅搬，則直接返回cur；
3）left和right中一個(gè)null脖旱，另一個(gè)不為null堪遂，說(shuō)明不為空的節(jié)點(diǎn)是n1和n2的其中一個(gè)，或者是n1和n2的最近公共祖先萌庆；則返回不為空的節(jié)點(diǎn)溶褪；
代碼
public class LowestAncestor {
/*求解n1和n1的最近公共祖先
*
* 利用后序遍歷求解
*/
public Node getLowestAncestor(Node head,Node n1,Node n2){
if(head==null || head==n1 || head==n2){
return head;
}
//先遍歷左右子樹(shù)，左右子樹(shù)的返回為left和right踊兜；然后判斷l(xiāng)eft和right請(qǐng)情況
Node left=getLowestAncestor(head.left,n1,n2);
Node right=getLowestAncestor(head.right,n1,n2);
/*左和右都不為null---說(shuō)明在左子樹(shù)中發(fā)現(xiàn)過(guò)n1或n2竿滨，
* 在右子樹(shù)上也發(fā)現(xiàn)過(guò)n1或n2佳恬，并且n1和n2在當(dāng)前節(jié)點(diǎn)首次相遇
*/
if(left!=null && right!=null){
return head;
}
/*左和右中一個(gè)不為null，另一個(gè)為null于游，
* 說(shuō)明不為null的節(jié)點(diǎn)是n1或n2中的一個(gè)毁葱，或者是n1和n2的最近祖先；
* 直接返回贰剥；
*/
if(left!=null){
return left;
}
if(right!=null){
return right;
}
//左和右均為null倾剿，沒(méi)有發(fā)現(xiàn)n1和n2；
return null;
}
}
遞歸理解
今天剛看到這個(gè)題目的遞歸解法時(shí)蚌成，感覺(jué)很繞前痘，覺(jué)得方法很好，可就是想不清楚遞歸遍歷到樹(shù)的更深層級(jí)的返回值應(yīng)該是什么担忧。實(shí)在沒(méi)辦法理解芹缔，拿筆畫(huà)了畫(huà)，終于get到點(diǎn)了瓶盛，就有了下一小結(jié)的遞歸執(zhí)行過(guò)程圖最欠。
實(shí)例分析
