力扣(LeetCode)113
題目地址:
https://leetcode-cn.com/probl...
題目描述:
給定一個二叉樹和一個目標和,找到所有從根節點到葉子節點路徑總和等於給定目標和的路徑。
說明: 葉子節點是指沒有子節點的節點。
示例:
給定如下二叉樹,以及目標和 sum = 22,
5 / \ 48 // \ 11134 /\/ \ 7251
返回:
[
[5,4,11,2],
[5,8,4,5]
]
解答:
遞迴。求以root為根並且和為sum的路徑等於。
1root為空,那麼為空(不存在這個路徑)。
2root為葉節點,並且sum等於root.val,返回root這個單節點路徑。
3以root的左子樹為根並且和為sum-root.val的路徑加上root(若該路徑存在)。
4以root的右子樹為根並且和為sum-root.val的路徑加上root(若該路徑存在)。
java ac程式碼: /** * Definition for a binary tree node. * public class TreeNode { *int val; *TreeNode left; *TreeNode right; *TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>>ans = new ArrayList(100); if(root == null)return ans; if(root.left == null && root.right == null && sum == root.val) { List<Integer> t = new LinkedList(); t.add(root.val); ans.add(t); return ans; } List<List<Integer>>t1 = pathSum(root.left,sum-root.val); List<List<Integer>>t2 = pathSum(root.right,sum-root.val); if(t1.size() > 0) { for(int i = 0;i < t1.size();i++) { LinkedList<Integer>t = (LinkedList)t1.get(i); t.addFirst(root.val); ans.add(t); } } if(t2.size() > 0) { for(int i = 0;i < t2.size();i++) { LinkedList<Integer>t = (LinkedList)t2.get(i); t.addFirst(root.val); ans.add(t); } } return ans; } }