I am currently trying to make a list of lists with all of the root to leaf paths in a binary tree. When I try writing out the result for the paths list and all of the recursive calls I can't seem to figure out where the error would lie. I thought of the idea of popping off of each individual path after hitting a leaf but that gave weird results as well. I also include the definition of the Tree Node which is the format for the input.
Current input: [1,2,3,null,5](1 is root, 2 and 3 are children of 1, and 5 is the right child of 2) Expected output: [[1,2,3],[1,3]] Current output: [[1,2,5,3],[1,2,5,3]]
Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def binaryTreePaths(self, root: Optional[TreeNode]):
if not root:
return
paths = []
def traverse(root,path,paths):
if not root:
return []
path.append(root.val)
if not root.left and not root.right:
paths.append(path)
traverse(root.left,path,paths)
traverse(root.right,path,paths)
traverse(root,[],paths)
return paths
If I'm not mistaken, you are doing this LC question. https://leetcode.com/problems/binary-tree-paths/
I have solved this question on LC, so pasting the modified version with comments.
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
# for empty root, return empty array
if not root:
return []
# variable to hold all paths
paths = []
def traverse(root,path,paths):
if not root:
return
# if root(node) is not empty, this node value will need to be added in current path
path.append(root.val)
# if the above node is leaf node,
# we have to make a copy of path (since list are mutable)
# and then pop the element of this current path as we back track
if not root.left and not root.right:
paths.append(path[:])
path.pop()
return
# if above node was not leaf node, then travese right and left
traverse(root.left,path,paths)
traverse(root.right,path,paths)
# once traversed, we backtrack by popping
path.pop()
traverse(root,[],paths)
return paths