题解 | #二叉树中和为某一值的路径(二)#
二叉树中和为某一值的路径(二)
https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @param target int整型 * @return int整型ArrayList<ArrayList<>> */ public ArrayList<ArrayList<Integer>> FindPath (TreeNode root, int target) { // write code here //二叉树的遍历,如果借助辅助空间,一般使用队列或者栈。看需要,队列就是分层遍历,栈就是前中后序遍历 //这个问题,可以退化成,链表之和为targetNumber的问题,链表就是这棵树从根到叶子,能发展多少条链表 //是不是按照中序遍历,把这个链表结合起来,但是展开成链表,还是需要递归的,不如直接在递归的过程中,把结果算一下,如果有问题,直接就丢弃了,没问题的路径保留,最后就可以直接返回结果了。 ArrayList<ArrayList<Integer>> resultList = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> levelList = new ArrayList<Integer>(); if(root == null){ return resultList; } FindSubPath(root, target, resultList, levelList); return resultList; } private void FindSubPath(TreeNode node, int target, ArrayList<ArrayList<Integer>> resultList, ArrayList<Integer> levelList) { // TODO if (node == null && target == 0) { resultList.add(levelList); return; } if (node == null && target != 0) { //说明次路径不符合。需要丢弃。如何丢弃呢?不往resultList里添加嘛 return; } ArrayList<Integer> levelListLeft = new ArrayList<Integer>(); levelListLeft.addAll(levelList); ArrayList<Integer> levelListRight = new ArrayList<Integer>(); levelListRight.addAll(levelList); levelListLeft.add(node.val); levelListRight.add(node.val); //这里要区别一下叶子节点和普通节点,叶子节点,左右子节点都为null,如果这样写,会+两遍集合进去,因此当叶子节点时,要剔除一次! if (node.left == null && node.right == null) { FindSubPath(node.left, target - node.val, resultList, levelListLeft); } else { FindSubPath(node.left, target - node.val, resultList, levelListLeft); FindSubPath(node.right, target - node.val, resultList, levelListRight); } } }