257. Binary Tree Paths
Apr 15, 2022
Check out the problem description here.
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
res=[]
ds=[]
self.rec(root,res,ds)
for i in range(len(res)):
res[i] = "->".join(res[i])
return(res)
def rec(self,root,res,ds):
if root ==None:
return
ds.append(str(root.val))
if root.left ==None and root.right==None:
res.append(ds.copy())
ds.pop(-1)
return
self.rec(root.left,res,ds)
self.rec(root.right,res,ds)
ds.pop(-1)
The above code in a much more neat code is given below
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
res=[]
if root:
self.rec(root,"",res)
return res
def rec(self,root,path,res):
if root == None :
return
path+=str(root.val)
if root.right==None and root.left ==None:
res.append(path)
return
self.rec(root.left,path+"->",res)
self.rec(root.right,path+"->",res)
Both solution takes the same time and complexity
TIME :O(n) n= number of nodes
SPACE :O(h) h = height of the tree