# 所有的路径

1 /
2 3
5

## 思路

（1）如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子节点。

（2）如果当前节点是叶子节点，则在当前路径末尾添加该节点后我们就得到了一条从根节点到叶子节点的路径，将该路径加入到答案即可。

## java 实现

public List<String> binaryTreePaths(TreeNode root) {
List<String> results = new ArrayList<>();
binaryTreePaths(results, new StringBuilder(), root);
return results;
}

private void binaryTreePaths(List<String> results, StringBuilder builder, TreeNode root) {
if(root == null) {
return;
}
builder.append(root.val);
// 叶子节点
if(root.left == null && root.right == null) {
}
builder.append("->");

// 左右子树
binaryTreePaths(results, new StringBuilder(builder), root.left);
binaryTreePaths(results, new StringBuilder(builder), root.right);
}


Runtime: 1 ms, faster than 99.81% of Java online submissions for Binary Tree Paths.
Memory Usage: 39.2 MB, less than 58.21% of Java online submissions for Binary Tree Paths.


### 复杂度

时间复杂度：O(N^2)



# 路径总和的路径

## 题目

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22


• 示例 2：

输入：root = [1,2,3], targetSum = 5


• 示例 3：
输入：root = [1,2], targetSum = 0



-1000 <= Node.val <= 1000

-1000 <= targetSum <= 1000

## 思路

（1）找到所有路径列表

（2）遍历路径列表，找到符合总和的路径。

## java 实现

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> allPaths = new ArrayList<>();
getAllPathSum(allPaths, new ArrayList<>(), root);

// 筛选符合条件的列表
List<List<Integer>> results = new ArrayList<>();
for(List<Integer> all : allPaths) {
if(isTargetList(all, targetSum)) {
}
}
return results;
}

private void getAllPathSum(List<List<Integer>> allPaths, List<Integer> tempList, TreeNode root) {
if(root == null) {
return ;
}
// 叶子
if(root.left == null && root.right == null) {
}
// 左右子树
getAllPathSum(allPaths, new ArrayList<>(tempList), root.left);
getAllPathSum(allPaths, new ArrayList<>(tempList), root.right);
}


private boolean isTargetList(List<Integer> list, int target) {
if(list.size() == 0) {
return false;
}
int sum = 0;
for(Integer integer : list) {
sum += integer;
}
return target == sum;
}


Runtime: 3 ms, faster than 14.56% of Java online submissions for Path Sum II.
Memory Usage: 41.5 MB, less than 21.94% of Java online submissions for Path Sum II.


## 优化思路一：直接计算

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> allPaths = new ArrayList<>();
getAllPathSum(allPaths, new ArrayList<>(), root, targetSum, 0);
return allPaths;
}

private void getAllPathSum(List<List<Integer>> allPaths, List<Integer> tempList,
TreeNode root, int targetSum, int currentSum) {
if(root == null) {
return ;
}
currentSum += root.val;
// 叶子
if(root.left == null && root.right == null && targetSum == currentSum) {
}
// 左右子树
getAllPathSum(allPaths, new ArrayList<>(tempList), root.left, targetSum, currentSum);
getAllPathSum(allPaths, new ArrayList<>(tempList), root.right, targetSum, currentSum);
}


Runtime: 2 ms, faster than 35.52% of Java online submissions for Path Sum II.
Memory Usage: 41.8 MB, less than 13.36% of Java online submissions for Path Sum II.


## 优化思路三：数组创建

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> allPaths = new ArrayList<>();
getAllPathSum(allPaths, new ArrayList<>(), root, targetSum, 0);
return allPaths;
}

private void getAllPathSum(List<List<Integer>> allPaths, List<Integer> tempList,
TreeNode root, int targetSum, int currentSum) {
if(root == null) {
return ;
}
currentSum += root.val;
// 叶子
if(root.left == null && root.right == null && targetSum == currentSum) {
}
// 左右子树
getAllPathSum(allPaths, tempList, root.left, targetSum, currentSum);
getAllPathSum(allPaths, tempList, root.right, targetSum, currentSum);
// 移除最后一个元素
tempList.remove(tempList.size()-1);
}


Runtime: 1 ms, faster than 99.97% of Java online submissions for Path Sum II.
Memory Usage: 39.3 MB, less than 80.84% of Java online submissions for Path Sum II.


# 是否包含路径总和

## 题目

• 示例 1：

• 示例 2：

• 示例 3：

树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000


## java 实现

public boolean hasPathSum(TreeNode root, int targetSum) {
return hasPathSum(new ArrayList<>(), root, targetSum, 0);
}

private boolean hasPathSum(List<Integer> tempList,
TreeNode root, int targetSum,
int currentSum) {
if(root == null) {
return false;
}
currentSum += root.val;
// 叶子
if(root.left == null && root.right == null && targetSum == currentSum) {
return true;
}
// 左右子树
return hasPathSum(tempList, root.left, targetSum, currentSum)
||
hasPathSum(tempList, root.right, targetSum, currentSum);
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Path Sum.
Memory Usage: 38.9 MB, less than 69.04% of Java online submissions for Path Sum.


# 任意长度路径之和

## 题目

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

10
/  \
5   -3
/ \    \
3   2   11
/ \   \
3  -2   1

1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11


## 思路一：穷举

（1）找到一棵树的所有路径

（2）遍历每一个路径，从前往后遍历，找到符合条件的结果。

public List<List<Integer>> allPathSums(TreeNode root) {
List<List<Integer>> allPaths = new ArrayList<>();
getAllPathSum(allPaths, new ArrayList<>(), root);
return allPaths;
}

private void getAllPathSum(List<List<Integer>> allPaths, List<Integer> tempList,
TreeNode root) {
if(root == null) {
return ;
}
// 叶子
if(root.left == null && root.right == null) {
}
// 左右子树
getAllPathSum(allPaths, tempList, root.left);
getAllPathSum(allPaths, tempList, root.right);
// 移除最后一个元素
tempList.remove(tempList.size()-1);
}


// 穷举
// 0 ... n-1，一个也算吗？
// 每个元素可以重复吗？
// 长度为1，尝试一遍？
// 长度为2，尝试一遍？
// ...
// 长度为n，尝试一遍？
private List<Integer> allList(List<Integer> list, int targetSum) {
List<Integer> results = new ArrayList<>();
return results;
}


## 思路2：双递归法

• 以当前节点作为头结点的路径数量

• 以当前节点的左孩子作为头结点的路径数量

• 以当前节点的右孩子作为头结点啊路径数量

### java 实现

public int pathSum(TreeNode root, int sum) {
if(root == null){
return 0;
}
int result = countPath(root,sum);
int a = pathSum(root.left,sum);
int b = pathSum(root.right,sum);
return result+a+b;
}

public int countPath(TreeNode root,int sum){
if(root == null){
return 0;
}
sum = sum - root.val;
int result = sum == 0 ? 1:0;
return result + countPath(root.left,sum) + countPath(root.right,sum);
}


（1）终止条件代码

if(root == null){
return 0;
}


（2）核心逻辑

sum 等于目标值：

sum = sum - root.val;
int result = sum == 0 ? 1:0;


### 效果

Runtime: 22 ms, faster than 25.58% of Java online submissions for Path Sum III.
Memory Usage: 39.2 MB, less than 29.40% of Java online submissions for Path Sum III.


# 前缀和

## 前缀和定义

      1
/  \
2    3
/ \    \
4   5    6
/ \   \
7   8   9


## 与本题的关系

两节点间的路径和 = 两节点的前缀和之差

       1
/
2
/
3
/
4


节点1的前缀和为: 1

prefix(3) - prefix(1) == 5



## HashMap存的是什么

HashMap的key是前缀和， value是该前缀和的节点数量，记录数量是因为有出现复数路径的可能。

    1
/
0
/
2


## 恢复状态的意义

      0
/  \
A:2  B:2
/ \    \
4   5    6
/ \   \
7   8   9


## java 实现

// key是前缀和, value是大小为key的前缀和出现的次数
Map<Integer, Integer> prefixMap;
int target;

public int pathSum(TreeNode root, int sum) {
prefixMap = new HashMap<>();
target = sum;
// 前缀和为0的一条路径
prefixMap.put(0, 1);
return recur(root, 0);
}

private int recur(TreeNode node, int curSum) {
// 1.递归终止条件
if(node == null) {
return 0;
}
// 2.本层要做的事情
int res = 0;
// 当前路径上的和
curSum += node.val;
// 看看root到当前节点这条路上是否存在节点前缀和加target为currSum的路径
// 当前节点->root节点反推，有且仅有一条路径，如果此前有和为currSum-target,而当前的和又为currSum,两者的差就肯定为target了
// currSum-target相当于找路径的起点，起点的sum+target=currSum，当前点到起点的距离就是target
res += prefixMap.getOrDefault(curSum - target, 0);
prefixMap.put(curSum, prefixMap.getOrDefault(curSum, 0) + 1);
// 3.进入下一层
int left = recur(node.left, curSum);
int right = recur(node.right, curSum);
res = res + left + right;
// 4.回到本层，恢复状态，去除当前节点的前缀和数量
prefixMap.put(curSum, prefixMap.get(curSum) - 1);
return res;
}


### 效果

Runtime: 2 ms, faster than 100.00% of Java online submissions for Path Sum III.
Memory Usage: 38.8 MB, less than 61.97% of Java online submissions for Path Sum III.


# 求根节点到叶节点数字之和

## 題目

https://leetcode-cn.com/problems/sum-root-to-leaf-numbers

输入：root = [1,2,3]



输入：root = [4,9,0,5,1]



• 树中节点的数目在范围 [1, 1000] 内

• 0 <= Node.val <= 9

• 树的深度不超过 10

## 思路1

（1）获取全路径

（2）遍历列表，构建对应的数字，直接累加即可。

1 * 10^3 + 2 * 10^2 + 3 * 10^1 + 4 * 10^0


### java 实现

public int sumNumbers(TreeNode root) {
List<List<Integer>> results = new ArrayList<>();
getAllPath(root, results, new ArrayList<>());
// 遍历构建
int sum = 0;
for(int i = 0; i < results.size(); i++) {
sum += calcInt(results.get(i));
}
return sum;
}

// 1 2 3 4 = 1 * 10^3 + 2*10^2 + 3*10 + 4;
private int calcInt(List<Integer> list) {
int sum = 0;
for(int i = 0; i < list.size(); i++) {
int pow = list.size() -1 - i;
sum += list.get(i) * Math.pow(10, pow);
}
return sum;
}

private void getAllPath(TreeNode node, List<List<Integer>> results,
List<Integer> tempList) {
if(node == null) {
return;
}
if(node.left == null && node.right == null) {
}
getAllPath(node.left, results, new ArrayList<>(tempList));
getAllPath(node.right, results, new ArrayList<>(tempList));
}


Runtime: 1 ms, faster than 28.21% of Java online submissions for Sum Root to Leaf Numbers.
Memory Usage: 36.9 MB, less than 30.13% of Java online submissions for Sum Root to Leaf Numbers.


## 思路2

    1
/ \
2   3
/\
4  5


第一步：1



### java 实现

private int sum = 0;
private int temp = 0;

public int sumNumbers(TreeNode root) {
calc(root);
return sum;
}
private void calc(TreeNode node) {
if(node == null) {
return;
}
temp = temp * 10 + node.val;
// 叶子
if(node.left == null && node.right == null) {
sum += temp;
}
// 递归子节点
calc(node.left);
calc(node.right);
// 返回上一层
temp /= 10;
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Sum Root to Leaf Numbers.
Memory Usage: 36.2 MB, less than 96.95% of Java online submissions for Sum Root to Leaf Numbers.


# 参考资料

https://leetcode.com/problems/binary-tree-paths/

【图解二叉树面试题】字节跳动面试题-二叉树的所有路径(两种实现)

437.路径总和III 递归方式