給你二叉樹的根節(jié)點(diǎn) root 和一個(gè)整數(shù)目標(biāo)和 targetSum ，找出所有 從根節(jié)點(diǎn)到葉子節(jié)點(diǎn) 路徑總和等于給定目標(biāo)和的路徑。

葉子節(jié)點(diǎn) 是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。

示例1

• 輸入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

• 輸出：[[5,4,11,2],[5,8,4,5]]

提示

• 樹中節(jié)點(diǎn)總數(shù)在范圍 [0, 5000] 內(nèi)

• -1000 <= Node.val <= 1000

• -1000 <= targetSum <= 1000

方法：深度優(yōu)先搜索

從根開始計(jì)算，到找到某個(gè)節(jié)點(diǎn)的解，深度優(yōu)先搜索（回溯）采用“一直向下走，走不通就掉頭”的思想，相當(dāng)于采用了“先跟遍歷”的方法來構(gòu)造搜索樹。

算法如下：

• 遞歸當(dāng)前節(jié)點(diǎn)，如果當(dāng)前節(jié)點(diǎn)為空，直接返回；

• 否則目標(biāo)和遞減，用于判斷是否滿足目標(biāo)和；

• 把當(dāng)前節(jié)點(diǎn)的值加入到每一個(gè)路徑集合中；

• 當(dāng)目標(biāo)和遞減到0并且當(dāng)前節(jié)點(diǎn)沒有子節(jié)點(diǎn)，說明滿足條件，直接把當(dāng)前路徑集合“復(fù)制”（因?yàn)槁窂郊鲜莿?dòng)態(tài)的）到結(jié)果集合中；

• 遞歸遍歷左/右子節(jié)點(diǎn)；

• 向上回溯，需要將當(dāng)前節(jié)點(diǎn)從路徑集合中移除；

• 遞歸遍歷整個(gè)樹節(jié)點(diǎn)完成后，返回結(jié)果集合；

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)，因?yàn)橐刃虮闅v所有的節(jié)點(diǎn)。

• 空間復(fù)雜度：O(n)，最差的情況下，所有節(jié)點(diǎn)的都滿足，即整個(gè)二叉樹都存到結(jié)果集合中。

END

繩鋸木斷，水滴石穿，贈(zèng)友人。

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。