112.Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and
sum = 22
,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1 複制
return true, as there exist a root-to-leaf path
5->4->11->2
which sum is 22.
題目大意：判斷是否存在一條從根節點到葉子的路徑，使得和等于sum;
解法：
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
if(root.left == null && root.right == null){
if (root.val == sum) return true;
else return false;
}else {
return hasPathSum(root.left,sum-root.val)|| hasPathSum(root.right,sum-root.val);
}
} 複制
113.Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and
sum = 22
,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1 複制
Return:
[
[5,4,11,2],
[5,8,4,5]
] 複制
題目大意：将所有滿足和為sum的路徑羅列出來。
解法：
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new LinkedList<>();
List<Integer> res_temp = new LinkedList<>();
pathSum_recursion(res_temp,root,sum,res);
return res;
}
public void pathSum_recursion(List<Integer> res_temp,TreeNode root, int sum,List<List<Integer>> res){
if (root == null) return;
res_temp.add(root.val);
if (root.right==null &&root.left==null&&root.val == sum) { //如果是葉子節點
res.add(new LinkedList<>(res_temp));
}
//不是葉子節點
pathSum_recursion(res_temp,root.left, sum-root.val,res);
pathSum_recursion(res_temp,root.right, sum-root.val,res);
res_temp.remove(res_temp.size()-1);
} 複制
437.Path Sum III
You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Return 3. The paths that sum to 8 are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11 複制
題目大意:問有多路徑滿足和為sum，注意這裡的路徑不一定要從root節點到葉子節點。
解法：
public int pathSum(TreeNode root, int sum) {
if (root == null) return 0;
return findPath(root,sum) + pathSum(root.left,sum)+pathSum(root.right,sum);
}
public int findPath(TreeNode node ,int sum){
if (node ==null) return 0;
int res = 0;
if (node.val == sum) {
res += 1;
}
return res+ findPath(node.left,sum - node.val)+findPath(node.right,sum - node.val);
}
複制
擴充：
列印二叉樹的所有路徑
解法：
public List<List<Integer>> binaryTreePaths(TreeNode root) {
List<List<Integer>> res = new LinkedList<>();
List<Integer> resTemp = new ArrayList<>();
binaryTreePathHelper(root,resTemp,res);
return res;
}
public void binaryTreePathHelper(TreeNode root,List<Integer> resTemp , List<List<Integer>> res){
if (root == null) return;
resTemp.add(root.val);
if (root.left == null && root.right== null){
res.add(new LinkedList<>(resTemp));
}
binaryTreePathHelper(root.left,resTemp,res);
binaryTreePathHelper(root.right,resTemp,res);
resTemp.remove(resTemp.size()-1);
} 複制
這個與《113.Path Sum II》類似，首先将節點添加進來，再判斷是否滿足條件，然後遞歸左右子樹，最後一定要删除掉最後一個元素。對應程式中的：
resTemp.remove(resTemp.size()-1); 複制
其實這個也就是一個回溯的過程，為了讓回溯的過程更加清楚，設定了一個測試用例：
5
/ \
3 6
/ \ \
2 4 7
/
1 複制
每一次執行 resTemp.remove(resTemp.size()-1);所删除的節點分别是：
1
2
4
3
7
6
5 複制
實際上也就是後序删除所有的節點。
原創聲明，本文系作者授權騰訊雲開發者社群發表，未經許可，不得轉載。如有侵權，請聯系 [email protected] 删除。