# 路径／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](https://leetcode.com/problems/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](https://leetcode.com/problems/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](https://leetcode.com/problems/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](https://leetcode.com/problems/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的思路
* [**改进**](https://leetcode.com/problems/longest-univalue-path/discuss/108175/java-solution-with-global-variable)就是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);
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://syjohnson11.gitbook.io/leetcode/4_binary_tree/binary_tree_maximum_path_sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.