257. Binary Tree Paths

Problem Statement

link: LeetCode.cn LeetCode

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:

Input: root = [1,2,3,null,5] Output: ["1->2->5","1->3"]

Input: root = [1] Output: ["1"]

Solution Approach

The algorithm uses a depth-first search (DFS) approach with a stack to explore all paths from the root to the leaves, building paths as it traverses the tree.

Algorithm

1. Depth-First Search (DFS): The algorithm uses DFS to traverse the tree, exploring as far down a branch as possible before backtracking.
2. Stack for Path Tracking: It employs two stacks—one for nodes and another for paths—to keep track of the current node and the path leading to it.
3. Path Construction: For each leaf node encountered, the algorithm constructs the complete path from the root to that leaf and adds it to the result list.

Complexity

time complexity: O(n) space complexity: O(n)

Implement

    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: Optional[TreeNode]) -> List[str]:
        if not root:
            return []
        stack = [(root, str(root.val))]
        res = []
        while stack:
            node, path = stack.pop()
            if not node.left and not node.right:
                res.append(path)
            if node.right:
                stack.append((node.right, path + "->" + str(node.right.val)))
            if node.left:
                stack.append((node.left, path + "->" + str(node.left.val)))
        return res

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        def dfs(node, path):
            if not node:
                return
            if not node.left and not node.right:
                res.append(path)
                return
            if node.left:
                dfs(node.left, path + "->" + str(node.left.val))
            if node.right:
                dfs(node.right, path + "->" + str(node.right.val))
        res = []
        if root:
            dfs(root, str(root.val))
        return res

    
    

Twitter  facebook  Email