题解 | #二叉树中和为某一值的路径#
二叉树中和为某一值的路径
http://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca
前序遍历二叉树,用list集合存储所经过的节点值
将当前节点值加入list,判断从根节点到当前节点和目标和的大小关系
1.大于或者此节点为null,返回。否则将当前节点加入list
2.等于,判断是否已经是叶子节点,是将当前集合加入结果集,
3.小于,继续去找当前节点的左右子节点进行判断
4.从list删除当前节点,返回,
public class Solution { public ArrayList<ArrayList<Integer>> res=new ArrayList(); public ArrayList<Integer> list=new ArrayList(); public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { dfs(root,target); return res; } public void dfs(TreeNode root,int target){ //(1) if(root==null||target-root.val<0){ return; } list.add(root.val);//加入当前节点值 if(target-root.val==0&&root.left==null&&root.right==null){ res.add(new ArrayList(list)); //(2)加入结果集 } //递归(3) dfs(root.left,target-root.val); dfs(root.right,target-root.val); list.remove(list.size()-1); //(4)回溯 } }