二叉树-257二叉树的所有路径带回溯思想

257. 二叉树的所有路径

 1 # Definition for a binary tree node.
 2 # class TreeNode:
 3 #     def __init__(self, val=0, left=None, right=None):
 4 #         self.val = val
 5 #         self.left = left
 6 #         self.right = right
 7 class Solution:
 8     def binaryTreePaths(self, root: TreeNode) -> List[str]:
 9         path = ''
10         result = []
11         if not root: return result
12         self.traversal(root, path, result)
13         return result
14     
15     def traversal(self, cur: TreeNode, path: str, result: List[str]) -> None:
16         path += str(cur.val)
17         # 若当前节点为leave，直接输出
18         if not cur.left and not cur.right:
19             result.append(path)
20             #return
21 
22         if cur.left:
23             # + '->' 是隐藏回溯
24             #，貌似没有看到回溯的逻辑，其实不然，回溯就隐藏在traversal(cur->left, path + "->", result);中的 path + "->"。 每次函数调用完，path依然是没有加上"->" 的，这就是回溯了。
25             self.traversal(cur.left, path + '->', result)
26         
27         if cur.right:
28             self.traversal(cur.right, path + '->', result)