Leetcode刷题——路径总和

概述

记录了112. 路径总和、 113. 路径总和 II、437. 路径总和 III。
都是用递归完成的，里面有一些细节，还是通过递归思路进行分析。

112. 路径总和

题目：112. 路径总和
这里有特定的条件，就是根节点到叶子结点。所以只需要看到到叶子结点的时候，目标值是否已经剪为0。
直接从代码分析

//为什么有返回值这里递归可以用返回值？还是之前那说的，因为要用到返回值。
//为什么这里可以把参数写到方法体中？因为在整个方法体中，要的就是当前的targetSum，并不会受前后的影响。
public boolean hasPathSum(TreeNode root, int targetSum) {
    
	//终止条件
    if(root == null) return false;
    //函数体，当前该节点到叶子结点还需要的大小。
    targetSum-=root.val;
    //找到了对应的值，终止条件
    if(root.left ==null && root.right == null){
    
        return targetSum == 0;
    }
    //左右子树右一个对的即可，这里用到了返回值。
    return hasPathSum(root.left,targetSum) || hasPathSum(root.right,targetSum);
}

113. 路径总和 II

题目：113. 路径总和 II
这题和之前不一样的地方是需要找到所有的路径。
那么就需要用一个list来保存。听起来和之前差不多，但是与很多需要注意的地方，在代码中详细说明。

	//为什么放在递归的方法体外面而不放在里面，因为每次都要求是最新的
	private List<List<Integer>> res = new ArrayList<>();
    List<Integer> list =new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    
    find(root,targetSum);
        return res;
    }
    //为什么没有返回值，因为不需要用，这里需要的是递归找到所有的结果，并不需要对返回值进行处理。
    private void find(TreeNode root, int targetSum ){
    
        if(root == null){
    
            return;
        }	
        //将当前节点算入其中。
        list.add(root.val);
        targetSum-=root.val;
        if(root.left ==null && root.right == null){
    
            if( targetSum == 0){
    
				//这里一定要new ！！！
				//否则存的是一个引用
                res.add(new ArrayList(list));
            }
        }
        find(root.left,targetSum);
        find(root.right,targetSum);
        //当前节点处理过了，就把它移除。
        list.remove(list.size()-1);
    }

437. 路径总和 III

题目：437. 路径总和 III
这道题去掉了根节点和叶子结点的条件，顺延上面的思路，只需要把每个节点都可以作为叶子节点和根节点就可以了。但是其实中间出过一个问题，就是会出现重复情况。
比如:

如果目标节点是4的话，1-2 会到4
但是从1分出来那个分支也就是直接从2开始也会到达4，4就被计数了两次。
直接上代码进行分析

	int sum = 0;
    public int pathSum(TreeNode root, int targetSum) {
    
        judge(root,targetSum,true);
        return sum;
    }
    //两个参数放在方法体上，因为是一个局部的,并不是全局的。
     public void judge(TreeNode root, long count, boolean isStartNode) {
    
        if (root == null) {
    
            return;
        }
        if (count == root.val) {
    
            sum++;
        }
        //这里是头节点,如果true才能继续
        //防止多次当头的情况发生
        //这样递归的话，每个点都有的当头的机会。
        if (isStartNode ){
    
            judge(root.left, count, true);
            judge(root.right, count,  true);
        }
        //头节点确定的时候，往下搜索。
        //下面的节点都不是头节点，不需要走上面这个判断逻辑。isStartNode设置为false
        if (root.left != null) {
    
            judge(root.left, count-root.val, false);
        }
        if (root.right != null) {
    
            judge(root.right, count-root.val,  false);
        }
    }