二叉树中和为某一值的所有路径

问题描述

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为整数的所有路径。路径定义为从树的根结点开始往下一直到叶子结点所经过的结点形成一条路径

思路分析

从问题描述知道，前序遍历符合从根结点遍历，所有可用此方法遍历，同时可以设置两个集合，一个用来保存每次遍历的结点，一个用来记录每次访问过的结点路径，如果等于和的话，就将结点路径加入，如果不等于，则看是否有左右孩子，在递归遍历，最后如果，返回上层，每一次都要删掉保存的结点

码上有戏

public ArrayList<ArrayList<Integer>> findPath(TreeNode root,int target){
		  int currentSum=0;
		  ArrayList<Integer> nodes=new ArrayList<Integer>();
		   ArrayList<ArrayList<Integer>> pathNodes=new ArrayList<>();
		    if(root==null)
		    	return pathNodes;
		      return findPath(pathNodes,nodes,root,target,currentSum);
	}

	private ArrayList<ArrayList<Integer>> findPath(ArrayList<ArrayList<Integer>> pathNodes, ArrayList<Integer> nodes,
			TreeNode root, int target, int currentSum) {
	         currentSum+=root.data;
	          nodes.add(currentSum);
	         
	        boolean isLeafNode=(root.left==null)&&(root.right==null);
	          if(target==currentSum&&isLeafNode){
	        	 ArrayList<Integer> path=new ArrayList<Integer>();
	        	  for(Integer val:nodes)
	        	  {
	        		  path.add(val);
	        	  }
	        	  pathNodes.add(path);
	         }
	         if(root.left!=null){
	        	 this.findPath(pathNodes, nodes, root.left, target, currentSum);
	         }
	         if(root.right!=null){
	        	 this.findPath(pathNodes, nodes, root.right, target, currentSum);
	         }
	         Integer value=nodes.remove(pathNodes.size()-1);
	          currentSum-=value;
	           return pathNodes;
	}

}
 class TreeNode{
	int data;
	TreeNode left;
	TreeNode right;
	
	TreeNode(int data){
		this.data=data;
	}
}

测试：

TreeNode a=new TreeNode(10);
TreeNode b=new TreeNode(5);
TreeNode c=new TreeNode(12);
TreeNode d=new TreeNode(4);
TreeNode e=new TreeNode(7);
a.left=b;
a.right=c;
b.left=d;
b.right=e;
ArrayList> pathNodes=new ConstructBinaryTree().findPath(a, 19);
for(ArrayList list:pathNodes)
for(Integer val:list){
System.out.println(val+” “);
}