由于路径是从根节点到叶节点的，因此我们需要先遍历根节点。在树的前序、中序、后序3种遍历方式中，只有前序遍历是首先访问根节点的。按照前序遍历的顺序遍历一个二叉树，在访问根节点后，会访问左子节点，并且我们知道在本题的二叉树节点中没有指向根节点的指针，所以当访问左子节点时我们不知道之前经过了什么节点，除非我们把经过的路径上的节点都保存下来。每访问一个节点，我们都把当前节点添加到路径中去。继续遍历，当遇到叶节点时将路径上的节点值的和与目标值相比较，若路径上节点值的和与目标值不等，则先将叶节点弹出路径列表，若遍历到某个叶节点时路径上的节点值和为目标值，则记录该路径。以此类推遍历整个二叉树。我们不难看出保存路径的数据结构实际上是一个栈。代码如下。自己一遍几乎没错写下来了（除了完了考虑空二叉树），以及不知道为什么没加list（）就只在答案里加了[]，迷惑（啊看到了大家的讨论，原因见下的引用段落，应该是深浅复制的问题）。这个算法的时间复杂度是O（N），空间复杂度是O（N）。
记录路径时若直接执行res.append(path)，则是将path列表对象加入了res；后续path对象改变时，res中的path对象 也会随之改变（因此肯定是不对的，本来存的是正确的路径path，后面又append又pop的，就破坏了这个正确路径）。list(path)相当于新建并复制了一个path列表，因此不会受到path变化的影响。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
self.target = sum
self.stack, self.ans = [], []
self.dfs(root)
return self.ans
def dfs(self, node):
if not node:
return
self.stack.append(node.val)
if not node.left and not node.right and sum(self.stack) == self.target:
self.ans.append(list(self.stack))
self.dfs(node.left)
self.dfs(node.right)
self.stack.pop()PREVIOUSlc102.二叉树的层序遍历
NEXTlc113.路径总和II