給定一棵二叉樹(保證非空)以及這棵樹上的兩個(gè)節(jié)點(diǎn)對(duì)應(yīng)的val值 o1 和 o2,請(qǐng)找到 o1 和 o2 的最近公共祖先節(jié)點(diǎn)。 數(shù)據(jù)范圍:樹上節(jié)點(diǎn)數(shù)滿足 , 節(jié)點(diǎn)值val滿足區(qū)間 [0,n) 要求:時(shí)間復(fù)雜度 注:本題保證二叉樹中每個(gè)節(jié)點(diǎn)的val值均不相同。 如當(dāng)輸入{3,5,1,6,2,0,8,#,#,7,4},5,1時(shí),二叉樹{3,5,1,6,2,0,8,#,#,7,4}如下圖所示: 所以節(jié)點(diǎn)值為5和節(jié)點(diǎn)值為1的節(jié)點(diǎn)的最近公共祖先節(jié)點(diǎn)的節(jié)點(diǎn)值為3,所以對(duì)應(yīng)的輸出為3。 節(jié)點(diǎn)本身可以視為自己的祖先
示例1
輸入
{3,5,1,6,2,0,8,#,#,7,4},5,1
示例2
輸入
{3,5,1,6,2,0,8,#,#,7,4},2,7
加載中...