剑指offer17 JZ82 二叉树中和为某一值的路径(一)

深度优先遍历+回溯

1. 首先，深度优点遍历来说，先写上一个回溯 if (curNode == null) { return false; }，这表示递归至最深层开始回溯，至于为什么 return false 后面再讲
2. 每次进入函数时，将 sum 减去当前节点的权重(curNode.val)，当 sum 减到零时，说明目标路径存在，另外我们的目标是到叶子节点停止，叶子节点的条件是 curNode.left == null && curNode.right == null，所以说当 if (curNode.left == null && curNode.right == null && target == 0) ，我们返回 true 表示找到目标路径
3. 深度遍历的分支：对于当前节点 curNode 有两个分支，这两个分支都有可能成为目标路径，所以深度优先遍历的写法为 return dfs(curNode.left, target) || dfs(curNode.right, target);
4. 现在来谈谈为什么回溯时需要返回 false，因为当 curNode 为叶子节点时，并且 sum == 0 时，我们已经返回了 true，剩下的情况就是 curNode 不是叶子节点或者路径值不为 target，所应该返回 false

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        if(root==null){
            return false;
        }
        return dfs(root,sum);
        // write code here
    }
    public boolean dfs(TreeNode cur,int target){
        if(cur==null){
            //回溯
            return false;
        }
        target-=cur.val;
        //减到为0 且为叶子节点 就找到了路径
        if(cur.left==null && cur.right==null && target==0){
            return true;
        }
        //左右节点进行dfs
        return dfs(cur.left,target)||dfs(cur.right,target);
        
    }
}