1. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:

Given the below binary tree and

sum = 22

,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path5->4->11->2which sum is 22.

public class Solution {

    public boolean hasPathSum(TreeNode root, int sum) {

        if(root == null) return false;
        else if(root.left == null && root.right == null && root.val == sum) return true;
        else return hasPathSum(root.left, sum - root.val) || 
                    hasPathSum(root.right, sum - root.val);
    }
}

2. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:

Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {

        ArrayList<List<Integer>> ans = new ArrayList<>();
        if(root == null) return ans;

        dfs(root, sum, new ArrayList<>(), ans);
        return ans;
    }

    public void dfs(TreeNode root, int sum, List<Integer> sub, ArrayList<List<Integer>> ans) {

        if(root == null)
            return ;

        sub.add(root.val);

        if(root.left == null && root.right == null && sum == root.val){

            ans.add(new ArrayList<>(sub));
        }
        else{

            dfs(root.left, sum - root.val, sub, ans);
            dfs(root.right, sum - root.val, sub, ans);
        }

        sub.remove(sub.size() - 1);
    }
}

3. Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must containat least one nodeand does not need to go through the root.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return6.

public class Solution {

    int max_value = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {

        if(root == null) return 0;
        maxSum(root);
        return max_value;
    }

    public int maxSum(TreeNode root) {

        if(root == null) return 0;

        int left = Math.max(0, maxSum(root.left));
        int right= Math.max(0, maxSum(root.right));

        max_value = Math.max(max_value, root.val + left + right);

        return root.val + Math.max(left, right);
    }
}

4. Sum Root to Leaf Numbers

Given a binary tree containing digits from0-9only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path1->2->3which represents the number123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path1->2represents the number12.
The root-to-leaf path1->3represents the number13.

Return the sum = 12 + 13 =25.

public class Solution {
    public int sumNumbers(TreeNode root) {

        if(root==null) return 0;
        return sum(root, 0);
    }

    public int sum(TreeNode root, int sum) {
        if(root==null) return 0;
        if(root.left==null && root.right==null) return sum*10+root.val;
        else return sum(root.left,sum*10 + root.val) + sum(root.right,sum*10 + root.val);
    }
}

public class Solution {
    public int sumNumbers(TreeNode root) {

        if(root==null) return 0;

        dfs(root, new StringBuilder());
        return ans;
    }

    int ans = 0;

    public void dfs(TreeNode root, StringBuilder sub) {

        if(root == null) return;

        sub.append(root.val);

        if(root.left == null && root.right == null){
            ans += Integer.valueOf(sub.toString());
        }
        else{
            dfs(root.left, sub);
            dfs(root.right, sub);
        }

        sub.deleteCharAt(sub.length() - 1);
    }
}