leetcode112:路径总和

思路

采用递归
1.判断终止条件
到达叶子节点且targetSum=0即有一条路径符合，因为最后都减到0了，返回true，否则到达叶子节点但targetSum不为0则返回false）
2.确定单层递归
如果左节点不为空，就从左边遍历，反之则从右边，有回溯的思想在里面，将左边用回溯的思想写就是这样
if (root.left) { // 左
targetSum -= root.left.val; // 递归，处理节点;
if (traversal(root.left, targetSum)) return true;
targetSum+= root.left.val; // 回溯，撤销处理结果
}

JS语言

var hasPathSum = function(root, targetSum) {
//采用递归的方法
    const traversal = (root, targetSum) => {
    if(!root.left&&!root.right&&targetSum===0){
        return true;
    }
    if(!root.left&&!root.right){
        return false;
    }
    if(root.left) { // 左 （空节点不遍历）
    // 遇到叶子节点返回true，则直接返回true
        if(traversal(root.left, targetSum-root.left.val)) return true; // 注意这里有回溯的逻辑
}
    if(root.right) { // 右 （空节点不遍历）
    // 遇到叶子节点返回true，则直接返回true
        if(traversal(root.right, targetSum-root.right.val)) return true; // 注意这里有回溯的逻辑
}
return false;
     };
    if (!root) return false;
    if (!root.left && !root.right && targetSum === root.val) return true;
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);