Path Sum, Path Sum II, Binary Tree Maximum Path Sum, Binary Tree Paths, Sum Root to Leaf Numbers

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 path 5->4->11->2 which sum is 22.

Recursive Solution

public boolean hasPathSum(TreeNode root, int sum) {
    return dfs(root, sum);
}
private boolean dfs(TreeNode root, int sum){
    if(root==null) return false;
    sum = sum-root.val;
    if(root.left==null && root.right==null) return sum==0;
    return dfs(root.left, sum) || dfs(root.right, sum);
}

Iterative Solution

• Use two queues to store all possible sum and curnode pairs
• when reached a leave, check if the corresponding sum is true

public boolean hasPathSum(TreeNode root, int sum) {
    if(root==null) return false;
    LinkedList<TreeNode> node = new LinkedList<TreeNode>();
    LinkedList<Integer> value = new LinkedList<Integer>();
    node.offer(root);
    value.offer(root.val);
    while(!node.isEmpty()){
        TreeNode cur = node.poll();
        int cursum = value.poll();
        if(cur.left==null && cur.right==null && cursum==sum){
            return true;
        }
        if(cur.left!=null) {
            node.offer(cur.left);
            value.offer(cursum+cur.left.val);
        }
        if(cur.right!=null){
            node.offer(cur.right);
            value.offer(cursum+cur.right.val);
        }
    }
    return false;   
}

---

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]
]

DFS Solution

public ArrayList<LinkedList<Integer>> pathSum(TreeNode root, int sum) {
    ArrayList<LinkedList<Integer>> res = new ArrayList<LinkedList<Integer>>();
    if(root==null) return res;
    LinkedList<Integer> pathlist = new LinkedList<Integer>();
    dfs(root, sum, pathlist, res);
    return res;
}

private void dfs(TreeNode r, int sum, LinkedList<Integer> pathlist, ArrayList<LinkedList<Integer>> res){
    pathlist.add(r.val);
    int curvalue = sum-r.val;
    if(r.left==null && r.right==null && curvalue==0) {res.add(new LinkedList<Integer>(pathlist));}
    if(r.left!=null) dfs(r.left, curvalue, pathlist, res);
    if(r.right!=null) dfs(r.right, curvalue, pathlist, res);
    pathlist.remove(pathlist.size()-1); //**
}

---

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,

       1
      / \
     2   3
Return 6.

DFS + DP Solution

• Return each time the max single path starting from current r
• update maxsofar among single/arc of current r

public int maxPathSum(TreeNode root) {
    int[] maxsofar = new int[1];
    maxsofar[0]= Integer.MIN_VALUE;
    dfs(root,maxsofar);
    return maxsofar[0];
}

private int dfs(TreeNode r, int[] maxsofar){
    if(r==null) return 0;
    int left = dfs(r.left, maxsofar);
    int right = dfs(r.right, maxsofar);
    int arc = left + right + r.val;
    int single = Math.max(r.val, Math.max(left, right)+r.val);
    maxsofar[0] = Math.max(maxsofar[0], Math.max(single,arc));
    return single;
}

---

Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:

   1
 /   \
2     3
 \
  5
All root-to-leaf paths are:
["1->2->5", "1->3"]

Solution

public List<String> binaryTreePaths(TreeNode root) {
    List<String> res = new ArrayList<String>();
    if(root==null) return res;
    StringBuilder sb = new StringBuilder();
    dfs(root, res, sb);
    return res;
}
private void dfs(TreeNode root, List<String> res, StringBuilder sb){
    if(root.left==null && root.right==null){
        sb.append(root.val);
        res.add(sb.toString());
        return;
    }
    sb.append(root.val);
    sb.append("->");
    if(root.left!=null){
        dfs(root.left, res, new StringBuilder(sb));
    }
    if(root.right!=null){
        dfs(root.right, res, new StringBuilder(sb));
    }
}

---

Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,

1

/ \
2 3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.

Solution

public int sumNumbers(TreeNode root) {
       ArrayList<Integer> path=new ArrayList<Integer>();
       List<List<Integer>> res=new ArrayList<List<Integer>>();
       if(root==null) return 0;
       dfs(root, path, res);
       return getsum(res);
   }
   
   private static void dfs(TreeNode cur, ArrayList<Integer> path, List<List<Integer>> res){
       path.add(cur.val);
       if(cur.left==null && cur.right==null){
           res.add(new ArrayList<Integer>(path));
           path.remove(path.size()-1);
           return;
       }
       if(cur.left!=null){
           dfs(cur.left, path, res);
       }
       if(cur.right!=null){
           dfs(cur.right, path, res);
       }
       path.remove(path.size()-1);
   }
   
   private int getsum(List<List<Integer>> res){
       int sum=0;
       for(List<Integer> path: res){
           int subsum=0;
           for(int i=0;i<path.size();i++){
               subsum=10*subsum+path.get(i);
           }
           sum+=subsum;
       }
       return sum;
   }