和bsf没有任何关系，leetcode相似题112，113，129，404的，简单。
113，backtracking
public class Solution {
public int minPathSum(TreeNode root) {
if(root == null) return 0;
return helper(root);
}
public int helper(TreeNode root){
if(root == null) return Integer.MAX_VALUE;
if(root.left == null && root.right == null ) return root.val;
return Math.min(helper(root.left),helper(root.right)) + root.val;
}
}
- Binary Tree Paths
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res=new ArrayList<>();
if(root==null) return res;
dfs(res,"",root);
return res;
}
public void dfs(List<String> res,String s,TreeNode root){
if(root.left==null&&root.right==null) res.add(s+root.val);
if(root.left!=null) dfs(res,s+root.val+"->",root.left);
if(root.right!=null) dfs(res,s+root.val+"->",root.right);
}
}
- Path Sum
public class Solution {
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);
}
}
- Path Sum II
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res=new ArrayList<>();
if(root==null) return res;
dfs(root,sum,res,new ArrayList<>());
return res;
}
public void dfs(TreeNode root,int sum,List<List<Integer>> res,List<Integer> list){
list.add(root.val);
if(root.left==null&&root.right==null&&sum==root.val){
res.add(new ArrayList<>(list));
list.remove(list.size()-1);
return;
}
if(root.left!=null) dfs(root.left,sum-root.val,res,list);
if(root.right!=null) dfs(root.right,sum-root.val,res,list);
list.remove(list.size()-1);
}
}
- Sum Root to Leaf Numbers
public class Solution {
public int sumNumbers(TreeNode root) {
return sum(root,0);
}
public int sum(TreeNode root,int sum){
if(root==null) return 0;
if(root.left==null&&root.right==null) return root.val+sum*10;
return sum(root.left,sum*10+root.val)+sum(root.right,sum*10+root.val);
}
}
- Sum of Left Leaves
public class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root==null) return 0;
int ans=0;
if(root.left!=null){
if(root.left.left==null&&root.left.right==null) ans+=root.left.val;
else ans+=sumOfLeftLeaves(root.left);
}
if(root.right!=null){
ans+=sumOfLeftLeaves(root.right);
}
return ans;
}
}
