路徑總和 II

題目描述：給你二叉樹的根節(jié)點 root 和一個整數(shù)目標和 targetSum ，找出所有 從根節(jié)點到葉子節(jié)點 路徑總和等于給定目標和的路徑。

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

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/path-sum-ii/ ??

著作權歸領扣網(wǎng)絡所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權，非商業(yè)轉(zhuǎn)載請注明出處。

解法一：層序遍歷

用Queue<Pair<TreeNode, Pair<Integer, List<Integer>>>>這種結(jié)構(gòu)來記錄當前節(jié)點的路徑以及路徑和，其中：

• 外層的Pair的key為當前節(jié)點；

• 內(nèi)層的Pair的key為當前路徑的總和，value為當前路徑的記錄，從根節(jié)點到當前節(jié)點。

然后使用層序遍歷的方式使用隊列遍歷二叉樹的節(jié)點，當判斷某節(jié)點的左右節(jié)點為空，即為葉子節(jié)點，然后判斷當前的路徑值是否與targetSum相等，如果相等，將相應的路徑添加到結(jié)果集中。

最后，返回結(jié)果集。

【每日寄語】 命運，不過是失敗者無聊的自慰，不過是懦怯者的解嘲。人們的前途只能靠自己的意志、自己的努力來決定。