Twenty five of offer - all paths with a certain value in the binary tree

Title Description

• Enter a binary tree and an integer , Print out the sum of node values in the binary tree as all paths of input integers .
• Path is defined as a path formed from the root node of the tree to the node that the leaf node passes through .

analysis

• The first sequence traversal , Put the traversed node into A Collection
• When the leaf node is traversed and the sum is exactly the target value , Put all nodes traversed into B Collection ,B Is a path to meet the meaning of the topic
• If the sum of leaf nodes is still not equal to the target value , Then remove it A Nodes added to the collection , Modifications and , Switch to the right child node and recalculate
• If you do not traverse to the leaf node, continue to look for such a path from the child node

Binary tree definition

class TreeNode {
    
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
    
        this.val = val;

    }

}

Code implementation

public ArrayList<ArrayList<Integer>> findPath(TreeNode root,int target) {
    
    /* * currentSum  Record current and  * pathNodes  Save the nodes scanned by the current path  * pathList  Save the paths that meet the conditions  */
	int currentSum = 0;
	ArrayList<Integer> pathNodes = new ArrayList<Integer>();
	ArrayList<ArrayList<Integer>> pathList = new ArrayList<ArrayList<Integer>>();
	
	if(root == null){
    
		return pathList;
	}
	
	return findPath(pathList,pathNodes,root,target,currentSum);
}


private ArrayList<ArrayList<Integer>> findPath(
		ArrayList<ArrayList<Integer>> pathList,
		ArrayList<Integer> pathNodes,
		TreeNode root, 
		int target, 
		int currentSum) {
    
	
	currentSum += root.val;
	pathNodes.add(root.val);
	boolean isLeafNode = root.left == null && root.right == null;
	// If it is a leaf node and equal to the target value , Add the current path to pathList in 
	if(currentSum == target && isLeafNode){
    
		ArrayList<Integer> nodes = new ArrayList<Integer>();
		for(Integer node : pathNodes){
    
			nodes.add(node);
		}
		pathList.add(nodes);
	}
	// If it is not a leaf node, it will traverse its child nodes 
	if(root.left != null){
    
		findPath(pathList, pathNodes, root.left, target, currentSum);
	}
	if(root.right != null){
    
		findPath(pathList, pathNodes, root.right, target, currentSum);
	}
	
	// Before returning to the parent node , Delete the current node on the path 
	Integer node = pathNodes.remove(pathNodes.size() - 1);
	currentSum -= node;
	
	
	return pathList;
}