Tree-----找出和等于给定数字的所有路径（113. Path Sum II）

原题目

主要就是一个深度优先，深度优先本来就是用来解决图的问题

1.原题目

public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> result = new ArrayList<>(); List<Integer> item = new ArrayList<>(); if (root == null) { return result; } dfs(root, sum, item, result); return result; } public void dfs(TreeNode root, int sum, List<Integer> item, List<List<Integer>> result) { //临界条件，注意不是在这里进行result判断，结束条件是叶子节点而不是空节点 if (root == null) { return; } item.add(root.val); sum -= root.val; if (root.left == null && root.right == null) { if (sum == 0) { result.add(new ArrayList<>(item)); } } else { //尝试各种情况并进入下一状态 if (root.left != null) { dfs(root.left, sum, item, result); } if (root.right != null) { dfs(root.right, sum, item, result); } } //回收尝试 item.remove(item.size() - 1); }

2.变形：求从根节点到所有叶子节点的路径

public List<List<Integer>> pathAll(TreeNode root){ List<List<Integer>> result=new ArrayList<>(); List<Integer> item=new ArrayList<>(); if(root==null){ return result; } dfs(root,item,result); return result; } public void dfs(TreeNode root,List<Integer> item,List<List<Integer>> result){ if(root==null){ return ; } item.add(root.val); if(root.left==null&&root.right==null){ result.add(new ArrayList<>(item)); }else { if(root.left!=null){ dfs(root.left,item,result); } if(root.right!=null){ dfs(root.right,item,result); } } item.remove(item.size()-1); }

3.求最长路径，最短路径

求出所有路径了，，，判断路径长短还不简单？