LeetCode 257. Binary Tree Paths

Description

https://leetcode.com/problems/path-crossing/

Given the root of a binary tree, return all root-to-leaf paths in any order.

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).

Leave a Reply

Your email address will not be published.