257. Binary Tree Paths
难度: 简单
刷题内容
原题连接
- https://leetcode.com/problems/binary-tree-paths
内容描述
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
解题方案
思路 1
递归+DFS
class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
def helper(node, cur_path):
if not node.left and not node.right: ## 到leaf了
res.append(cur_path+[node.val])
return
if node.left:
helper(node.left, cur_path+[node.val])
if node.right:
helper(node.right, cur_path+[node.val])
res = []
if not root:
return res
helper(root, [])
return ['->'.join([str(val) for val in path]) for path in res]
注意一点，很多人可能看到这里有好几次cur_path+[node.val]，觉得干嘛不直接写在最开头了，事实是这样做的话cur_path就已经变化了，因为要执行完if node.left才去执行if node.right，此时cur_path就不是原来的cur_path了。
