Path java with a value in binary tree
Title Description
Input the following node and an integer of a binary tree, and print out all paths in which the sum of node values in the binary tree is the input integer. Path is defined as a path from the root node of the tree to the node that the leaf node passes through. (Note: in the list of returned values, the array with large array length is first).
Code 1:
public class Solution { public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>(); if(root == null || root.val > target){ return list; } ArrayList<Integer> path = new ArrayList<Integer>(); findPath(root,target,list,path); return list; } private void findPath(TreeNode root, int target, ArrayList<ArrayList<Integer>> list, ArrayList<Integer> path) { //If the node is empty or the value is less than target, the path is cleared if(root == null || root.val > target){ path.clear(); }else if(root.val == target){//If the current node is equal to target and is a leaf node, it will be added to the path directly, otherwise the path will be cleared if(root.left == null && root.right==null) { path.add(root.val); list.add(path); }else{ path.clear(); } }else{ //When the value of the root node is less than the target, the recursion searches for its left and right subtrees path.add(root.val); ArrayList<Integer> path2 = new ArrayList<Integer>(); path2.addAll(path); target -= root.val; findPath(root.left,target,list,path); findPath(root.right,target,list,path2); } } }
Code 2: