Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1 / \2 3 \ 5
All root-to-leaf paths are:
["1->2->5", "1->3"]
本题可以用DFS或者BFS。
解法一: DFS
class Solution(object): def binaryTreePaths(self, root): """ :type root: TreeNode :rtype: List[str] """ if not root: return [] result = [] self.dfs(root, result, [str(root.val)]) return result def dfs(self, root, result, path): if root.left is None and root.right is None: result.append('->'.join(path)) return if root.right: path.append(str(root.right.val)) self.dfs(root.right, result, path) path.pop() if root.left: path.append(str(root.left.val)) self.dfs(root.left, result, path) path.pop()
这个解法中需要注意的是current path的初始值是[str(root.val)]而不是。这个很类似的解法使用了pop。
如果要不使用pop的话
class Solution(object): def binaryTreePaths(self, root): """ :type root: TreeNode :rtype: List[str] """ if not root: return [] result = [] self.dfs(root, result, [str(root.val)]) return result def dfs(self, root, result, path): if root.left is None and root.right is None: result.append('->'.join(path)) return if root.right: self.dfs(root.right, result, path+[str(root.right.val)]) if root.left: self.dfs(root.left, result, path+[str(root.left.val)])