1、DFS（其实就是回溯算法）
2、BFS （相当于把所以节点显示的枚举出来）
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def binaryTreePaths(self, root: TreeNode) -> List[str]: if not root: return [] #BFS queue = collections.deque() #将根节点和根节点的值都放入队列中 queue.append([root,[str(root.val)]]) res = [] while queue: #弹出节点和其结果信息 node,temp = queue.popleft() #如果这个节点是根节点,那么就添加到结果列表中 if not node.left and not node.right: res.append('->'.join(temp)) #如果左子树存在，那么再队列添加更新队列的信息和path的信息；右子树同理可得 if node.left: queue.append([node.left,temp+[str(node.left.val)]]) if node.right: queue.append([node.right,temp+[str(node.right.val)]]) return res #DFS 其实就是回溯算法,不过回溯算法用了一个列表,需要执行一个弹出操作 #我再写的时候没有再递归的时候调用subset的信息,所以出错。 #递归底层就是一个栈，所以要试探选择所有可能性必须要同步更新消息 def DFS(root, subset): if root: subset += str(root.val) #如果为叶子节点那就直接添加到结果集中去 if not root.left and not root.right: result.append(subset) else: subset += '->' DFS(root.left, subset) DFS(root.right, subset) result = [] DFS(root, '') return result
总结：二叉树的问题往往都是DFS和BFS是可以相互转换的，再DFS中栈的思路一定再脑子中，这样才能把很多问题都能进行建模。
