112. 路径总和
问题描述
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
解题思路
直接递归实现，从根节点开始，用targetSum不断的减去遍历到的每一个节点，一直减到符合条件的叶子节点时，targetSum为0。
注意处理二叉树退化为链表的情况。
代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null){
return targetSum == 0;
}
int newTarget = targetSum - root.val;
if(root.left == null){
return hasPathSum(root.right, newTarget);
}
if(root.right == null){
return hasPathSum(root.left, newTarget);
}
return hasPathSum(root.left, newTarget) || hasPathSum(root.right, newTarget);
}
}
113. 路径总和 II
问题描述
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
解题思路
找寻符合叶子条件的思路与上一题基本一致；在采用递归进行先序遍历时将路径节点保存下来即可。
注意：在每次回溯时需要移除最后一个节点
代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
List<Integer> list = new ArrayList<>();
getResult(root, targetSum, res, list);
return res;
}
public void getResult(TreeNode root, int targetSum, List<List<Integer>> res, List<Integer> list){
if(root == null){
return;
}
list.add(root.val);
targetSum = targetSum - root.val;
if(root.left == null && root.right == null && targetSum == 0){
//找到符合条件的叶子节点
res.add(new ArrayList<>(list));
//此时已将叶子节点添加至路径，进行回溯时需要移除叶子节点
list.remove(list.size() -1);
return;
}
getResult(root.left, targetSum, res, list);
getResult(root.right, targetSum, res, list);
//递归结束时，已将叶子节点添加至路径，进行回溯时需要移除
list.remove(list.size() -1);
}
}
