Description
Find all path to leaf node
Solution
Recursion
O(N) time & space
class Solution:
"""
@param root: the root of the binary tree
@return: all root-to-leaf paths
"""
def binaryTreePaths(self, root):
if root is None:
return []
if root.left is None and root.right is None:
return [str(root.val)]
leftPaths = self.binaryTreePaths(root.left)
rightPaths = self.binaryTreePaths(root.right)
paths = []
for path in leftPaths + rightPaths:
paths.append(str(root.val) + '->' + path)
return paths
如果只找一个
"""
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):
# write your code here
if root is None:
return []
if root.left is None and root.right is None:
return [str(root.val)]
left= []
if root.left is not None:
left =self.binaryTreePaths(root.left)
right =[]
if root.right is not None:
right = self.binaryTreePaths(root.right)
path =[]
for p in right+left:
path.append(str(root.val) + '->'+ p)
return path
