Java二叉树路径和代码示例

  1 / / 2 4 / / 2 3

[ [1, 2, 2], [1, 4]]

/** * Definition of TreeNode: * public class TreeNode { *  public int val; *  public TreeNode left, right; *  public TreeNode(int val) { *   this.val = val; *   this.left = this.right = null; *  } * } */public class Solution {	/**  * @param root the root of binary tree  * @param target an integer  * @return all valid paths  */	public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {		// Write your code here		return dfs(root,new ArrayList<Integer>(),0,new ArrayList<List<Integer>>(),target);	}	public List<List<Integer>> dfs(TreeNode root,List<Integer> node, int sum, List<List<Integer>> paths,int target)	 {		if(root==null)		  {			return new ArrayList<List<Integer>>();		}		List<List<Integer>> path=new ArrayList<List<Integer>>();		if(root.left!=null)		  {			List<Integer> nodes=new ArrayList<Integer>();			if(node!=null)			  {				nodes.addAll(node);			}			nodes.add(root.val);			List<List<Integer>> temp=dfs(root.left,nodes,sum+root.val,paths,target);			if(temp!=null)			   {				path.addAll(temp);			}		}		if(root.right!=null)		  {			List<Integer> nodes=new ArrayList<Integer>();			if(node!=null)			  {				nodes.addAll(node);			}			nodes.add(root.val);			List<List<Integer>> temp=dfs(root.right,nodes,sum+root.val,paths,target);			if(temp!=null)			   {				path.addAll(temp);			}		}		if(root.left==null&&root.right==null)		  {			List<Integer> nodes=new ArrayList<Integer>();			if(node!=null)			  {				nodes.addAll(node);			}			nodes.add(root.val);			if(sum+root.val==target)			   {				path.add(nodes);			} else{				path=new ArrayList<List<Integer>>();			}		}		return path;	}}