34-二叉树中和为某一值的路径

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

        本题要求的是从根节点到叶子节点的路径,所以满足条件的list集合,肯定第一个节点是根节点,最后一个节点是叶子节点。学习了力扣上大佬的解题思路,很巧妙。首先定义一个全局变量LinkedList<List<Integer>> list作为返回的所有路径的即可,再定义LinkedList<Integer> sublist作为某一条具体的路径的值的集合。在对树进行遍历的时候,如果该节点为空,则直接返回。如果不为空,则首先将该节点的值加到sublist,再判断该节点是不是叶子节点,以及是否满足和为target的条件,如果满足则重新new一个即可,并将sublist赋值给new出来的集合,并加到list上。若加到叶子节点都不满足,则把加在sublist上的val清除掉,继续遍历。

package learnproject.offer;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/*
 * 34.二叉树中和为某一值的路径
 */
public class Demo34 {

	public LinkedList<List<Integer>> list = new LinkedList();
	LinkedList<Integer> subList = new LinkedList();
	 public List<List<Integer>> pathSum(TreeNode root, int target) {
               recur(root,target);
               return list;
	 }
	 
	 public void recur(TreeNode node,int target) {
		 if(node == null) {
			 return;
		 }
		 subList.add(node.val);
		 target = target - node.val;
		 if(target == 0 && node.left ==null && node.right == null) {
			 list.add(new LinkedList(subList));
		 }
		 recur(node.left,target);
		 recur(node.right,target);
		 subList.removeLast();
	 }
	 
	 public static void main(String args[]) {
		 Demo34 demo = new Demo34();
		 TreeNode node1 = new TreeNode(5);
		 TreeNode node21 = new TreeNode(4);
		 TreeNode node22 = new TreeNode(8);
		 TreeNode node31 = new TreeNode(11);
		 TreeNode node32 = new TreeNode(13);
		 TreeNode node33 = new TreeNode(4);
		 TreeNode node41 = new TreeNode(7);
		 TreeNode node42 = new TreeNode(2);
		 TreeNode node43 = new TreeNode(5);
		 TreeNode node44 = new TreeNode(1);
		 node1.left= node21;
		 node1.right = node22;
		 node21.left = node31;
		 node22.left = node32;
		 node22.right = node33;
		 node31.right = node41;
		 node31.right = node42;
		 node33.left = node43;
		 node33.right = node44;
		 demo.pathSum(node1, 22);
		 LinkedList<List<Integer>> ttt = demo.list;
		 int size = demo.list.size();
		 for(int i=0;i<size;i++) {
			 System.out.println(Arrays.toString(ttt.get(i).toArray()));
		 }
	 }
	 
	
}

上一篇:大文件中数据排序问题


下一篇:List 各个实现类使用流程图