Do a DFS and save the path in a stack. Once we visit a leaf, we could copy the current stack as a valid path.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
self.stack = []
self.result = []
self._helper(root)
return ['->'.join(r) for r in self.result]
def _helper(self, node):
if node is None:
return
self.stack.append(str(node.val))
if node.left == node.right == None:
self.result.append(self.stack[:])
self._helper(node.left)
self._helper(node.right)
self.stack.pop()