前序和中序遍歷的結(jié)果层亿,就是兩個(gè)數(shù)組,比如:
前序 : 1立美、2匿又、4、3建蹄、5碌更、6
中序 : 4、2洞慎、1痛单、5、3劲腿、6
原理:
1.首先確定根節(jié)點(diǎn)的位置旭绒,前序遍歷的第一個(gè)位置就是根節(jié)點(diǎn),然后去中序遍歷中找到這個(gè)根節(jié)點(diǎn)的位置,根節(jié)點(diǎn)的左邊所有的數(shù)就是左子樹上的節(jié)點(diǎn)挥吵,右邊所有的節(jié)點(diǎn)就是右子樹上的節(jié)點(diǎn):
?2.對(duì)左子樹和右子樹同樣用上述方法遞歸的重建重父。
代碼(OC):
返回的值,就是根節(jié)點(diǎn)
驗(yàn)證忽匈,我是使用遞歸房午,分別打印各個(gè)節(jié)點(diǎn)的值,至于非遞歸的方式丹允,以后再寫