例1： LeetCode 第 257 题：二叉树的所有路径
传送门：257. 二叉树的所有路径。
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入: 1 / \ 2 3 \ 5 输出: ["1->2->5", "1->3"] 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
要求：给定一棵二叉树，返回所有表示从根结点到叶子结点路径的字符串。
关键：理解“回溯”在深度优先搜索里面的应用。
思路1：使用递归完成，中途记录路径，走到叶子结点的时候结算；
Python 代码：==特别注意：通过参数传递的方式，就没有显式的回溯的过程了==
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 257. 二叉树的所有路径
# 给定一个二叉树，返回所有从根结点到叶子结点的路径。
class Solution:
# 深度优先遍历，我感觉最好理解
# 参考：https://leetcode.com/problems/binary-tree-paths/discuss/68258/Accepted-Java-simple-solution-in-8-lines
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
res = []
if root is None:
return res
self.__helper(root, '', res)
return res
def __helper(self, node, pre, res):
if node.left is None and node.right is None:
res.append(pre + str(node.val))
return
# 特别注意：通过参数传递的方式，就没有显式的回溯的过程了
if node.left:
self.__helper(node.left, pre + str(node.val) + '->', res)
if node.right:
self.__helper(node.right, pre + str(node.val) + '->', res)
思路2：使用深度优先遍历，回溯的方式，一定要记住：一条路径走完以后，要弹出栈。
Python 代码：
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
res = []
if root is None:
return res
path = []
self.__helper(root, path, res)
return res
def __helper(self, node, path, res):
"""
:param node:
:param path: 沿途经过的结点值组成的列表
:param res: 存放最终结果的变量
:return:
"""
if node is None:
return
path.append(str(node.val))
if node.left is None and node.right is None:
# 可以结算了
res.append("->".join(path))
return
if node.left:
self.__helper(node.left, path, res)
# 【重点】：回溯的时候，要记得弹出
# 左边结点都看过了，所以 path 要弹出
path.pop()
if node.right:
self.__helper(node.right, path, res)
# 【重点】：回溯的时候，要记得弹出
# 右边结点都看过了，所以 path 要弹出
path.pop()
以上两种方法都使用了辅助函数，其实还可以不借助辅助函数，直接在原来的函数上做递归。
LeetCode 第 257 题：二叉树的所有路径
Python 代码：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
res = []
if root is None:
return []
if root.left is None and root.right is None:
res.append(str(root.val))
return res
left_paths = self.binaryTreePaths(root.left)
for lpath in left_paths:
res.append(str(root.val) + '->' + lpath)
right_paths = self.binaryTreePaths(root.right)
for rpath in right_paths:
res.append(str(root.val) + '->' + rpath)
return res
练习1：LeetCode 第 113 题：路径总和 II
传送门：英文网址：113. Path Sum II ，中文网址：113. 路径总和 II 。
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和sum = 22，5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1返回:
[ [5,4,11,2], [5,8,4,5] ]
思路：前序遍历。套路是使用辅助函数。中途保存路径，如果一条道走到底的话，要记得弹出。Python 中复制一个列表的方法有：
1、list(path)；
2、path * 1；
3、path[:]。
Python 代码：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# 使用 dfs 来解决
# 113. 路径总和 II
# 给定一个二叉树和一个目标和，找到所有从根结点到叶子结点路径总和等于给定目标和的路径。
# 解法 1 和 解法 2 是一回事。
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
results = []
self.__dfs([], root, sum, results)
return results
def __dfs(self, path, root, sum, results):
if root is None:
return
if root.left is None and root.right is None and root.val == sum:
result = []
result.extend(path)
result.append(root.val)
results.append(result)
return
path.append(root.val)
if root.left:
self.__dfs(path, root.left, sum - root.val, results)
if root.right:
self.__dfs(path, root.right, sum - root.val, results)
# 这一步很关键
path.pop()
练习2：LeetCode 第 129 题：求根到叶子结点数字之和
传送门：求根到叶子结点数字之和。
给定一个二叉树，它的每个结点都存放一个
0-9的数字，每条从根到叶子节点的路径都代表一个数字。例如，从根到叶子节点路径
1->2->3代表数字123。计算从根到叶子节点生成的所有数字之和。
说明: 叶子节点是指没有子节点的节点。
示例 1:
输入: [1,2,3] 1 / \ 2 3 输出: 25 解释: 从根到叶子节点路径 1->2 代表数字 12. 从根到叶子节点路径 1->3 代表数字 13. 因此，数字总和 = 12 + 13 = 25.示例 2:
输入: [4,9,0,5,1] 4 / \ 9 0 / \ 5 1 输出: 1026 解释: 从根到叶子节点路径 4->9->5 代表数字 495. 从根到叶子节点路径 4->9->1 代表数字 491. 从根到叶子节点路径 4->0 代表数字 40. 因此，数字总和 = 495 + 491 + 40 = 1026.
要求：给定一棵二叉树，每个结点只包含数字 0-9，从根结点到叶子结点的每条路径可以表示成一个数，求这些数的和。
Java 代码1：使用 path，递归回溯的常规解法。
// https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/description/
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
// 我的思路：使用深度优先遍历，遍历到根结点的时候，把数字加一加
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
private List<String> result = new ArrayList<>();
private void sumNumbers(TreeNode node, String path) {
if (node == null) {
return;
}
path = path + node.val;
if (node.left == null && node.right == null) {
// 才是叶子结点，执行我们的逻辑
result.add(path);
return;
}
sumNumbers(node.left, path);
sumNumbers(node.right, path);
}
private int convert() {
int sum = 0;
for (String s : result) {
sum += Integer.parseInt(s);
}
return sum;
}
public int sumNumbers(TreeNode root) {
if (root == null) {
return 0;
}
sumNumbers(root, "");
return convert();
}
public static void main(String[] args) {
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
n1.left = n2;
n1.right = n3;
Solution solution = new Solution();
int result = solution.sumNumbers(n1);
System.out.println("得到的结果：" + result);
}
}
Python 代码2（推荐）：（使用递归）使用 cumsum 这个概念，即开始遍历到这个根结点的之前，已经有了 cumsum ，代码写出来也是非常简洁。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sumNumbers(self, root):
"""
:type root: TreeNode
:rtype: int
"""
res = []
self.__dfs(root, 0, res)
return sum(res)
# Python 中对于基础的数据类型是值传递，即复制
def __dfs(self, root, cum_sum, res):
if root is None:
return None
if root.left is None and root.right is None:
# 结算
res.append(cum_sum * 10 + root.val)
return
self.__dfs(root.left, cum_sum * 10 + root.val, res)
self.__dfs(root.right, cum_sum * 10 + root.val, res)
Java 代码3：
// https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/description/
import java.util.ArrayList;
import java.util.List;
// 我的思路：这个写法，画个图就非常清晰了，抓住二叉树的特点
public class Solution2 {
private int sumNumbers(TreeNode node, int cumsum) {
if (node == null) {
return 0;
}
cumsum = 10 * cumsum + node.val;
if (node.left == null && node.right == null) {
return cumsum;
}
return sumNumbers(node.left, cumsum) + sumNumbers(node.right, cumsum);
}
public int sumNumbers(TreeNode root) {
if (root == null) {
return 0;
}
return sumNumbers(root, 0);
}
public static void main(String[] args) {
// write your code here
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
n1.left = n2;
n1.right = n3;
Solution2 solution2 = new Solution2();
int result = solution2.sumNumbers(n1);
System.out.println("得到的结果：" + result);
}
}
还有一种解法，修改了原二叉树的结点的值。
Python 代码：
# 129. 求根到叶子结点数字之和
# 给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子结点的路径都代表一个数字。
# 例如，从根到叶子结点路径 1->2->3 代表数字 123。
# 计算从根到叶子结点生成的所有数字之和。
# 说明: 叶子结点是指没有子结点的结点。
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def __init__(self):
self.res = 0
def sumNumbers(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
if root.left:
# 如果左边非空
root.left.val += root.val * 10
if root.right:
# 如果右边非空
root.right.val += root.val * 10
# 如果左边右边都为空，就可以结算了
if root.left is None and root.right is None:
self.res += root.val
# 前序遍历
self.sumNumbers(root.left)
self.sumNumbers(root.right)
return self.res
（本节完）
