Leetcode Brush Questions - Path Sum

概述

记录了112. 路径总和、 113. 路径总和 II、437. 路径总和 III.
It's all done with recursion,里面有一些细节,还是通过递归Analyse ideas.

112. 路径总和

题目：112. 路径总和
There are certain conditions here,It is from the root node to the leaf node.So you only need to see when the leaf node is reached,Whether the target value has been clipped to0.
Analysis directly from the code

//Why there is a return value here recursion can use return value？Still as said before,Because the return value is used.
//Why can the parameters be written into the method body here？Because in the entire method body,What is needed is currenttargetSum,It will not be affected by the front and back.
public boolean hasPathSum(TreeNode root, int targetSum) {
    
	//终止条件
    if(root == null) return false;
    //函数体,The current size of the node to the leaf node.
    targetSum-=root.val;
    //找到了对应的值,终止条件
    if(root.left ==null && root.right == null){
    
        return targetSum == 0;
    }
    //The left and right subtrees can be paired with the right one,The return value is used here.
    return hasPathSum(root.left,targetSum) || hasPathSum(root.right,targetSum);
}

113. 路径总和 II

题目：113. 路径总和 II
The difference between this question and the previous one is that all paths need to be found.
那么就需要用一个list来保存.Sounds about the same as before,But with a lot of caveats,Details in the code.

	//Why put it outside the recursive method body and not inside it,Because every time it is required to be up to date
	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;
    }
    //为什么没有返回值,Because it doesn't need to be used,What is needed here is to recursively find all the results,The return value does not need to be processed.
    private void find(TreeNode root, int targetSum ){
    
        if(root == null){
    
            return;
        }	
        //Count the current node into it.
        list.add(root.val);
        targetSum-=root.val;
        if(root.left ==null && root.right == null){
    
            if( targetSum == 0){
    
				//这里一定要new ！！！
				//Otherwise a reference is stored
                res.add(new ArrayList(list));
            }
        }
        find(root.left,targetSum);
        find(root.right,targetSum);
        //The current node has been processed,just remove it.
        list.remove(list.size()-1);
    }

437. 路径总和 III

题目：437. 路径总和 III
This question removes the conditions for the root and leaf nodes,Continuing the idea above,Just make each node can be used as a leaf node and a root node.But there was a problem in the middle,There will be repetitions.
比如:

如果目标节点是4的话,1-2 会到4
但是从1The branch that is branched out is directly from2The beginning will also arrive4,4was counted twice.
Go directly to the code for analysis

	int sum = 0;
    public int pathSum(TreeNode root, int targetSum) {
    
        judge(root,targetSum,true);
        return sum;
    }
    //Two parameters are placed on the method body,Because it is a local,并不是全局的.
     public void judge(TreeNode root, long count, boolean isStartNode) {
    
        if (root == null) {
    
            return;
        }
        if (count == root.val) {
    
            sum++;
        }
        //Here is the head node,如果true才能继续
        //Prevent multiple hits from happening
        //If so recursive,At every point there is an opportunity.
        if (isStartNode ){
    
            judge(root.left, count, true);
            judge(root.right, count,  true);
        }
        //When the head node is determined,往下搜索.
        //The following nodes are not head nodes,There is no need to follow the above judgment logic.isStartNode设置为false
        if (root.left != null) {
    
            judge(root.left, count-root.val, false);
        }
        if (root.right != null) {
    
            judge(root.right, count-root.val,  false);
        }
    }