二叉樹的所有路徑

題解：

這道題要求從根節(jié)點(diǎn)到葉子的路徑，所以需要前序遍歷，這樣才方便讓父節(jié)點(diǎn)指向孩子節(jié)點(diǎn)，找到對(duì)應(yīng)的路徑，因此涉及到了回溯。

1.遞歸函數(shù)及返回值

傳入根節(jié)點(diǎn)，記錄每一條路徑的path,存放結(jié)果集的result，不需要返回值

2.確定遞歸終止條件

當(dāng)左右孩子都為空的時(shí)候

3.確定單層遞歸邏輯

因?yàn)槭乔靶虮闅v，需要先處理中間節(jié)點(diǎn)，中間節(jié)點(diǎn)間就是我們要記錄路徑上的節(jié)點(diǎn)，先放進(jìn)path，然后遞歸和回溯的過(guò)程?；厮莺瓦f歸是一一對(duì)應(yīng)的，有一個(gè)遞歸，就要有一個(gè)回溯。

代碼：

左葉子之和

題解：

左葉子的明確定義：節(jié)點(diǎn)A的左孩子不為空，且左孩子的左右孩子都為空。判斷條件：if root.left and not root.left.left and not root.left.right

通過(guò)后序遍歷實(shí)現(xiàn)，因?yàn)橐ㄟ^(guò)遞歸函數(shù)的返回值來(lái)累加求取左葉子數(shù)值之和。

1.確定遞歸函數(shù)的參數(shù)和返回值

傳入樹的根節(jié)點(diǎn)，返回的是數(shù)值之和

2.終止條件

根節(jié)點(diǎn)是空，左葉子值一定是0

根節(jié)點(diǎn)的左右孩子為空，左葉子值一定是0

3.確定單層遞歸的邏輯

當(dāng)遇到左葉子節(jié)點(diǎn)的時(shí)候，記錄數(shù)值，然后通過(guò)遞歸求取左子樹左葉子之和，和右子樹左葉子之和，相加便是整個(gè)樹的左葉子之和

代碼：