问题描述：

 

Given a binary tree, return all root-to-leaf paths.

 

Note: A leaf is a node with no children.

 

Example:

 

Input:

   1
 /   \
2     3
 \
  5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

 

思路：

二叉树的问题，首先考虑递归算法，用深度优先搜索。

为了体现模块化思想，一般讲DFS算法单独写成一个方法

代码：

 

 1 # Definition for a binary tree node.
 2 # class TreeNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution:
 9     def dfs(self,res,root,list1):
10         if root.left == None and root.right == None:#当前节点是叶子节点
11             res.append( '->'.join(list1))
12             return 
13         if root.left != None:#左边不空
14             list1.append(str(root.left.val))
15             self.dfs(res,root.left,list1)
16             list1.pop()
17         if root.right != None:#右边不空
18             list1.append(str(root.right.val))
19             self.dfs(res,root.right,list1)
20             list1.pop()
21         
22     def binaryTreePaths(self, root):
23         """
24         :type root: TreeNode
25         :rtype: List[str]
26         """
27         if root == None:
28             return []
29         res = []
30         self.dfs(res,root,[str(root.val)])
31         return res

 

list1,res等不是方法内的局部变量，而是相当于一个全局变量，所以若方法改变其值，其值不论在哪一层次的调用中，都发生了相应改变