Given a binary tree, return all root-to-leaf paths.
Example 1:
Input:{1,2,3,#,5}
Output:["1->2->5","1->3"]
Explanation:
1
/ \
2 3
\
5
Example 2:
Input:{1,2}
Output:["1->2"]
Explanation:
1
/
2
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: the root of the binary tree
@return: all root-to-leaf paths
"""
def binaryTreePaths(self, root):
# call recursion
paths = self.dfs(root)
pathswords = ['->'.join(l[::-1]) for l in paths]
return pathswords
def dfs(self, node):
"""
in: node: TreeNode
out: paths: list of list of values, each sublist is a path
"""
# if no such a node:
if node is None:
return []
# return condition
if node.left is None and node.right is None:
return [[str(node.val)]]
# get answers
pathsLeft = self.dfs(node.left)
pathsRight = self.dfs(node.right)
# conbine answers
paths = pathsLeft + pathsRight
for p in paths:
p.append(str(node.val))
# return conbined answer
return paths
special care
A.insert()
and A.extend()
do not have return valueinsert(0, )
is a bad practice. I would rather reverse the list while using the accumulated list
pathswords = ['->'.join(l[::-1]) for l in paths]
p.append(str(node.val))
p.insert(0, str(node.val))