路径总和-112
题目描述
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。
叶子节点 是指没有子节点的节点。
解题思路
我们这题采用任何一种遍历方式都是可以的,这题同样是有回溯的思想,如果不太懂的话可以去看看前面《求二叉树的左右路径》这一题,我们先去遍历左子树,遍历的时候如果节点的左右子树都为空说明我们已经到了叶子节点,此时我们就可以做判断了,看看是不是和我们的targetSum一致,如果不一致则它的父节点会产生回溯去遍历父节点的另一个子树,同样再去看看是否和targetSum是否一致,如果一致就可以直接填写结果,不一致则继续由它们的父节点回溯去判断另一颗子树。
代码实例
class Solution {
public boolean judge = false;
public boolean hasPathSum(TreeNode root, int targetSum) {
List<Integer> list = new ArrayList<>();
if(root==null){
return false;
}else{
list.add(root.val);
bianli(root, targetSum, list);
return judge;
}
}
public void bianli(TreeNode root, int targetSum, List<Integer> list) {
if (root.left == null && root.right == null) {
if (sum(list) == targetSum) {
judge = true;
return;
}
}
if (root.left != null) {
list.add(root.left.val);
bianli(root.left, targetSum, list);
list.remove(list.size() - 1);
}
if (root.right != null) {
list.add(root.right.val);
bianli(root.right, targetSum, list);
list.remove(list.size() - 1);
}
}
public int sum(List<Integer> list) {
int sum = 0;
for (Integer in : list) {
sum += in;
}
return sum;
}
}