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);//回溯,画个递归树就理解了
}
}