路径／Path Sum

一步到位

• Path Sum II

List：

• Binary Tree Paths

• path sum I, II, III, IV

• sum root to leave numbers

• sum of left leaves

• binary tree maximum path sum

• Longest Univalue path

• Second Minimum Node In a Binary Tree

• All Nodes Distance K in Binary Tree（好题）

Binary Tree Paths

• 路径题的backtracking模板

• 这题还需要注意"->"的处理

public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if(root == null) return res;
        helper(root, res, new StringBuilder());
        return res;
    }
    private void helper(TreeNode root, List<String> res, StringBuilder sb){
        if(root == null){
            return;
        }
        int len = sb.length();
        sb.append(root.val);
        if(root.left == null && root.right == null){
            res.add(sb.toString());
        }else{
            sb.append("->");
            helper(root.left, res, sb);
            helper(root.right, res, sb);
        }
        sb.setLength(len);
    }
}

2018/10/01
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root == null) return res;
        helper(res, new StringBuilder(), root);
        return res;

    }
    private void helper(List<String> res, StringBuilder sb, TreeNode cur) {
        sb.append(Integer.toString(cur.val));
        if (cur.left == null && cur.right == null) {
            res.add(sb.toString());
        }
        int len = sb.length();
        if (cur.left != null) {
            sb.append("->");
            helper(res, sb, cur.left);
            sb.setLength(len);
        }
        if (cur.right != null) {
            sb.append("->");
            helper(res, sb, cur.right);
            sb.setLength(len);
        }

    }
 }

Path Sum

• 判断root.left == null && root.right == null && sum - root.val == 0

• 不用先求max depth

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

Path Sum II （好题）

• backTracking入门好题

• 找出所有的path which sum up to target

• backtracking, DFS查找

• 有加必有减

• 即使找到了结果也不能直接return

• 要等着把最后一个remove来判断是否还有其它满足条件的可能

public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        helper(res, new ArrayList<Integer>(), root, 0, sum);
        return res;
    }
    private void helper(List<List<Integer>> res, List<Integer> list, TreeNode root, int sum, int target){
        if(root == null) return;
        //if(sum > target) return;//如果没有负数，可以加上
        list.add(root.val);//有加必有减

        if(root.left == null && root.right == null && sum + root.val == target){
            res.add(new ArrayList<Integer>(list));//即使找到了结果也不能直接return,要等着把最后一个remove来判断是否还有其它满足条件的可能
        }else{
            helper(res, list, root.left, sum + root.val, target);
            helper(res, list, root.right, sum + root.val, target);
        }

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

• 另一种 解法

• 针对cur node需要判断三种情况

  • cur node is a child node-> check whether sum is equal to target

  • cur.left != null ->先加后减

  • cur.right != null -> 先加后减

2018/10/01
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        List<Integer> list = new ArrayList<Integer>();
        list.add(root.val);
        helper(res, list, root, sum - root.val);
        return res;
    }
    private void helper(List<List<Integer>> res, List<Integer> list, TreeNode cur, int target) {
        if (cur.left == null && cur.right == null) {
            if (target == 0) {
                res.add(new ArrayList<Integer>(list));
            }
            return;
        }
        if (cur.left != null) {
            list.add(cur.left.val);
            helper(res, list, cur.left, target - cur.left.val);
            list.remove(list.size() - 1);
        }
        if (cur.right != null) {
            list.add(cur.right.val);
            helper(res, list, cur.right, target - cur.right.val);
            list.remove(list.size() - 1);
        }
    }
}

Path Sum III

• 找满足条件的sub path的个数，不一定从root开始，从leaf结束，但是必须是向下的一个subPath

• 这题要干两件事

  • 计算从root开始到cur child node的path sum == target的cnt

  • 遍历每个node,以每个node为root都findPath( )，把结果累加上

• 所以其实应该有一个findPathNumber的题目过渡下会更好

• 只是recursion/ D&C, 不涉及backtracking

public class Solution {
    public int pathSum(TreeNode root, int sum) {
        if(root == null) return 0;
        return findPath(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    //return the number of path from root to cur that sum equal to target
    private int findPath(TreeNode root, int sum){
        if(root == null) return 0;
        int res = 0;
        if(root.val == sum){
            res++;
        }
        res += findPath(root.left, sum - root.val);
        res += findPath(root.right, sum - root.val);
        return res;
    }
}

Path Sum IV

Sum root to leaf numbers

• 做完Path Sum II之后发现这题跟那题思路一样

public class Solution {

    public int sumNumbers(TreeNode root) {
        if(root == null) return 0;
        int[] res = new  int[1];
        int[] tmp = new int[1];
        helper(res, tmp, root);
        return res[0];
    }
    private void helper(int[] res, int[] tmp, TreeNode root){
        if(root == null) return;
        int tmpp = tmp[0];
        tmp[0] = tmp[0] * 10 + root.val;
        if(root.left == null && root.right == null){
            res[0] += tmp[0];
        }else{
            helper(res, tmp, root.left);
            helper(res, tmp, root.right);
        }
        tmp[0] = tmpp;
    }
}

Sum of left leaves

• 先找root.left这个点，不为空的话判断它是否是leaf node,如果是就把结果加上

• 如果root.left不是leaf node, 就res += sumofLeftLeaves(root.left)

• 然后判断root.right是否为空，如果不是，就res += sumofLeftLeaves(root.right)

• 感觉这题的recursive的思路跟inOrderSuccessorof BST很像

public int sumOfLeftLeaves(TreeNode root) {
        //find left leaves
        //then sum up
        if(root == null) return 0;
        int res = 0;
        if(root.left != null){
            if(root.left.left == null && root.left.right == null){
                res += root.left.val;
            }else{
                res += sumOfLeftLeaves(root.left);
            }
        }
        if(root.right != null){
            res += sumOfLeftLeaves(root.right);
        }
        return res;
    }

• 这题的Iterative的解法

public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        Stack<TreeNode> stk = new Stack<>();
        int res = 0;
        stk.push(root);
        while(!stk.isEmpty()){
            TreeNode node = stk.pop();
            if(node.left != null){
                if(node.left.left == null && node.left.right == null){
                    res += node.left.val;
                }else{
                    stk.push(node.left);
                }
            }
            if(node.right != null){
                stk.push(node.right);
            }
        }
        return res;
    }

Binary Tree Maximum Path Sum

• 这题属于没做过很难想的题目

• 因为treenode会包含负数

• 借着建立public int maxSumSinglePath(TreeNode root, int[] max)和计算single path max sum ending with curnode

• 来获得maximum path sum, max[0]

public class Solution {
    public int maxPathSum(TreeNode root) {
        if(root == null) return Integer.MIN_VALUE;
        int[] max = new int[1];
        max[0] = Integer.MIN_VALUE;
        maxSumSinglePath(root, max);
        return max[0];
    }
    //return the max sum of single path, including root
    private int maxSumSinglePath(TreeNode root, int[] max){
        if(root == null) return 0;
        int left = Math.max(0, maxSumSinglePath(root.left, max));//since single path might be negative
        int right = Math.max(0, maxSumSinglePath(root.right, max));
        max[0] = Math.max(max[0], root.val + left + right);
        return root.val + Math.max(left, right);
    }
}

//2018/07/11 version
class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxSum(root);
        return max;
    }
    // get maxSum value ending with cur node
    private int maxSum(TreeNode root) {
        if (root == null) return 0;
        int left = Math.max(0, maxSum(root.left)); // 0 means not picking left subtree
        int right = Math.max(0, maxSum(root.right));
        // left and right must be non-negative value
        max = Math.max(max, left + right + root.val);
        return root.val + Math.max(left, right); // here can only pick one subtree path, not root.val + left + right
    }
}

Longest Univalue Path

• 套用max path sum的思路

• 改进就是helper(TreeNode node, int val) 里把parent node.val传进来比较

class Solution {
    int max = 0;
    public int longestUnivaluePath(TreeNode root) {
        helper(root);
        return max;
    }
    private int helper(TreeNode root) {
        if (root == null) return 0;
        int left = helper(root.left);
        int right = helper(root.right);
        if (root.left != null && root.left.val == root.val) {
            left = left + 1;
        } else {
            left = 0;
        }
        if (root.right != null && root.right.val == root.val) {
            right = right + 1;
        } else {
            right = 0;
        }
        max = Math.max(max, left + right);
        return Math.max(left, right);
    }
}

Second minimum node in a Binary Tree

class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null || root.left == null) return -1;
        int left = root.left.val;
        int right = root.right.val;
        if (left == root.val) {
            left = findSecondMinimumValue(root.left);
        }
        if (right == root.val) {
            right = findSecondMinimumValue(root.right);
        }
        if (left != -1 && right != -1) {
            return Math.min(left, right);
        } 
        // left(right) == -1 means find the minimum Value
        return Math.max(left, right);
    }
}

All Nodes Distance K in Binary Tree

• 用一个hashmap来存储从root到target的path上的所有node, val存距离target的距离

• 然后traverse tree, 如果遇到hashmap 里的node, 就用map.get(cur)的值来更新当前的距离

class Solution {
    Map<TreeNode, Integer> map = new HashMap<>();
    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        //use hashmap to store all the node from root path to target
        //value will be the distance from target
        findDistance(root, target);
        List<Integer> res = new ArrayList<>();
        dfs(root, target, K, map.get(root), res);
        return res;
    }
    private int findDistance(TreeNode cur, TreeNode target) {
        if (cur == null) return -1;
        if (cur == target) {
            map.put(cur, 0);
            return 0;
        }
        int left = findDistance(cur.left, target);
        if (left >= 0) {
            map.put(cur, left + 1);
            return left + 1;
        }
        int right = findDistance(cur.right, target);
        if (right >= 0) {
            map.put(cur, right + 1);
            return right + 1;
        }
        return -1;
    }
    private void dfs(TreeNode root, TreeNode target, int K, int len, List<Integer> res) {
        if (root == null) return;
        if (map.containsKey(root)) len = map.get(root);
        if (K == len) {
            res.add(root.val);
            //return;
        }
        dfs(root.left, target, K, len + 1, res);
        dfs(root.right, target, K, len + 1, res);
    }
}