标签（空格分隔）： 二叉树 深度优先遍历
传送门：113. 路径总和 II。
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和sum = 22，5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1返回:
[ [5,4,11,2], [5,8,4,5] ]
分析：使用深度优先遍历，用递归方法实现，所以递归的终止条件要写清楚，另外不要忘记状态的恢复。
Python 代码：
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def findPath(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
res = []
if root is None:
return res
self.__dfs(root, sum, [], res)
return res
def __dfs(self, node, residue, path, res):
# 递归，就应该先写递归终止条件
if node is None:
return
# 走到这里 node 肯定非空，所以可以使用 left 和 right 成员变量
# 走完以后，要记得回溯，状态要重置
# 先把它加到路径中，在各种 if 都不成立的最后，要记得 pop 出去
path.append(node.val)
if node.left is None and node.right is None:
# 如果是叶子结点，并且 residue 就等于当前结点的值
if node.val == residue:
res.append(path[:])
# 注意：这里不要 return ，如果要 return，return 之前把 path 执行 pop 操作
# 走到这里是非叶子结点，所以左边要走一走，右边也要走一走
if node.left:
self.__dfs(node.left, residue - node.val, path, res)
if node.right:
self.__dfs(node.right, residue - node.val, path, res)
path.pop()
另一种等价的写法：
Python 代码：
class Solution(object):
def findPath(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
res = []
if root is None:
return res
self.__dfs(root, sum, [], res)
return res
def __dfs(self, node, residue, path, res):
if node is None:
return
path.append(node.val)
residue -= node.val
if node.left is None and node.right is None and residue == 0:
# 才用结算
res.append(path[:])
path.pop()
return
if node.left:
self.__dfs(node.left, residue, path, res)
if node.right:
self.__dfs(node.right, residue, path, res)
path.pop()
（本节完）
