路径问题总结

257二叉树的所有路径

class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> ans = new ArrayList<>();dfs(root,"",ans);return ans;}private void dfs(TreeNode root,String path,List<String> ans){//递归终止条件if(root==null)  return;//如果是叶子节点，说明找到了一条路径if(root.left==null&&root.right==null){ans.add(path+root.val);return;}dfs(root.left,path+root.val+"->",ans);dfs(root.right,path+root.val+"->",ans);}
}

112 路径总和

 public boolean hasPathSum(TreeNode root, int sum) {//递归终止条件if(root==null)  return false;if(root.left==null&&root.right==null)return sum==root.val;return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);}

113 路径总和II

class Solution {public List<List<Integer>> pathSum(TreeNode root, int sum) {List<List<Integer>> ans = new ArrayList<>();dfs(root,sum,new ArrayList<>(),ans);return ans;}private void dfs(TreeNode root,int sum,List<Integer> list,List<List<Integer>> ans){//递归终止条件if(root==null)  return;List<Integer> sublist = new ArrayList<>(list);sublist.add(new Integer(root.val));if(root.left==null&&root.right==null){//到达叶子节点，表示找到了一组路径if(sum==root.val)ans.add(sublist);return; }dfs(root.left,sum-root.val,sublist,ans);dfs(root.right,sum-root.val,sublist,ans);}
}

437 路径总和III

437 路径总和III
关键点 targetsum只能改成long 不然会越界
在这里插入图片描述

在这里插入图片描述

class Solution {public int pathSum(TreeNode root, long targetSum) {//访问每一个节点 node，检测以node为起始节点且向下延深的路径有多少种if(root==null)  return 0;int count = root_sum(root,targetSum);//下面两行错在并没有递归找，只找了根 左，右三个为起点的// count+=root_sum(root.left,targetSum);// count+=root_sum(root.right,targetSum);count+=pathSum(root.left,targetSum);count+=pathSum(root.right,targetSum);return count;}//表示以节点p为起点向下且满足路径和为targetsum的路径数目private int root_sum(TreeNode p,long targetSum){int count =0;if(p==null) return 0;//这道题不需要到叶节点 才判断找到一条路径// if(p.left==null&&p.right==null)// {//     if(p.val==targetSum)//     return;// }if(p.val==targetSum)count++;count+=root_sum(p.left,targetSum-p.val);count+=root_sum(p.right,targetSum-p.val);return count;}
}

988. 从叶结点开始的最小字符串

class Solution {String ans ="~";//~ ascill码为126，大于所有A-Z.a-z,相当于一开始给个最大值public String smallestFromLeaf(TreeNode root) {dfs(root, new StringBuilder());return ans;}private void dfs(TreeNode node,StringBuilder sb){if(node==null)  return;sb.append((char)('a'+node.val));//到达叶节点，表达已经找到一条路径if(node.left==null&&node.right==null){sb.reverse();String s = sb.toString();if(s.compareTo(ans)<0)//比较字典序 如果更小就更新ans=s;sb.reverse();//比较完后再换回来，好接着递归}dfs(node.left,sb);dfs(node.right,sb);sb.deleteCharAt(sb.length()-1);//回溯，画个递归树就理解了}
}