二叉树中和为某一值的路径-java路径
二叉树中和为某一值的路径
http://www.nowcoder.com/questionTerminal/b736e784e3e34731af99065031301bca
一. 思路
递归先序遍历二叉树,遍历的过程中判断累加和是否为指定值,是则返回
二. 代码
import java.util.ArrayList; /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { ArrayList<ArrayList<Integer>> result = new ArrayList<>(); if (root == null){ return result; } ArrayList<Integer> path = new ArrayList<>(); this.find(root, target, result, path); return result; } private void find(TreeNode root, int target, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> path) { // 0,当节点为空,return if (root == null) { return; } path.add(root.val); target -= root.val; // 1,当目标值小于0,return if(target < 0){ return; } // 2,当目标值为0 并且 节点下无其他节点, 保存并返回 if(target == 0 && root.left == null && root.right == null){ result.add(path); return; } // 继续遍历左右节点 // 这里new path是因为左右都会在下次递归path.add(root.val); this.find(root.left, target, result, new ArrayList<>(path)); this.find(root.right, target, result, new ArrayList<>(path)); } }