输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
本题要求的是从根节点到叶子节点的路径,所以满足条件的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()));
}
}
}