題目

給定一個(gè)樹(shù)的根節(jié)點(diǎn)root和兩個(gè)子節(jié)點(diǎn)a,b，返回二叉樹(shù)中兩個(gè)節(jié)點(diǎn)的最低公共祖先。二叉樹(shù)每個(gè)節(jié)點(diǎn)的值都是不同的整數(shù)

       10060     12040 null  4 7

4和7的最低公共祖先是120，60和40的最低公共祖先是60

思路

兩個(gè)節(jié)點(diǎn)的祖先會(huì)有多個(gè)，只有是祖先的節(jié)點(diǎn)才有可能會(huì)是最低公共祖先。所以不是祖先的節(jié)點(diǎn)可以不用再去遍歷。

1. 遍歷節(jié)點(diǎn)并查找當(dāng)前節(jié)點(diǎn)的所有子節(jié)點(diǎn)數(shù)據(jù)，判斷節(jié)點(diǎn)是不是組先，
2. 如果不是祖先，該節(jié)點(diǎn)無(wú)需再繼續(xù)遍歷
3. 如果是祖先節(jié)點(diǎn)，將祖先節(jié)點(diǎn)加入list，繼續(xù)遍歷該節(jié)點(diǎn)左子節(jié)點(diǎn)和右子節(jié)點(diǎn)
4. 返回最后一個(gè)list元素，就是最低的公共祖先

代碼實(shí)現(xiàn)

import java