Description
https://leetcode.com/problems/path-crossing/
Given the root of a binary tree, return all root-to-leaf paths in any order.
A leaf is a node with no children.
Example 1:
Input: root = [1,2,3,null,5] Output: ["1->2->5","1->3"]
Example 2:
Input: root = [1] Output: ["1"]
Constraints:
- The number of nodes in the tree is in the range
[1, 100]. -100 <= Node.val <= 100
Explanation
Traverse the tree and track the root to leaf paths.
Python Solution
# 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
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
self.results = []
if not root:
return self.results
self.traverse(root, [str(root.val)])
return self.results
def traverse(self, root, path):
if not root.left and not root.right:
path_str = "->".join(path)
self.results.append(path_str)
return
if root.left:
path.append(str(root.left.val))
self.traverse(root.left, path)
path.pop()
if root.right:
path.append(str(root.right.val))
self.traverse(root.right, path)
path.pop()- Time Complexity: O(N).
- Space Complexity: O(N).