給定一個二叉樹和一個目標(biāo)和，找到所有從根節(jié)點到葉子節(jié)點路徑總和等于給定目標(biāo)和的路徑。

說明:?葉子節(jié)點是指沒有子節(jié)點的節(jié)點。

示例:
給定如下二叉樹，以及目標(biāo)和?sum = 22，

? ? ? ? ? ? ? 5
? ? ? ? ? ? ?/ \
? ? ? ? ? ? 4 ? 8
? ? ? ? ? ?/ ? / \
? ? ? ? ? 11 ?13 ?4
? ? ? ? ?/ ?\ ? ?/ \
? ? ? ? 7 ? ?2 ?5 ? 1
返回:

[
? ?[5,4,11,2],
? ?[5,8,4,5]
]

思路：dfs+回溯

提交的代碼：

/**

?*?Definition?for?a?binary?tree?node.

?*?public?class?TreeNode?{

?*?????int?val;

?*?????TreeNode?left;

?*?????TreeNode?right;

?*?????TreeNode(int?x)?{?val?=?x;?}

?*?}

?*/

class?Solution?{

????List<List<Integer>>?result?=?new?ArrayList<List<Integer>>();

?????List<Integer>?list?=?new?ArrayList<Integer>();

?????int?count=0;

????public?void?fun(TreeNode?root,?int?sum)

????{

????????if(count==sum&&root.left==null&&root.right==null)

????????{

????????????result.add(new?ArrayList<>(list));? //不能寫result.add(list);因為list會改變，帶動result也發(fā)生改變，需要復(fù)制一份到result

????????}

????????if(root.left!=null)

????????{

????????????list.add(root.left.val);

????????????count+=root.left.val;

????????????fun(root.left,sum);

????????}

????????if(root.right!=null)

????????{

????????????list.add(root.right.val);

????????????count+=root.right.val;

????????????fun(root.right,sum);

????????}

????????count-=list.get(list.size()-1);

????????list.remove(list.size()-1);

????????

????}

????public?List<List<Integer>>?pathSum(TreeNode?root,?int?sum)?{

???????

????????if(root!=null)

????????{

????????????list.add(root.val);

????????????count+=root.val;

????????????fun(root,sum);

????????}

????????return?result;

????}

}

總結(jié)

以上是生活随笔為你收集整理的Leetcode--113. 路径总和Ⅱ的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。