路径／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);
    }
}

Previous修改结构 NextBottom-Up

Last updated 4 years ago

Was this helpful?