257. Binary Tree Paths Easy

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"]

Approach

Input: The root node of a binary tree root.

Output: Return all root-to-leaf paths in any order.

This problem belongs to Depth-First Search (DFS) + Path Tracking + Backtracking problems.

Method 1: Recursive DFS + Backtracking

Taking advantage of DFS, we use an array path during the recursion to keep track of the current path in real time.

• For every node visited, add the node to the path;
• If the current node is a leaf node, join the path array into a string and add it to the result set;
• After visiting the left and right subtrees of the current node, use path.pop() to reverse the modification (backtrack);
• Recursively traverse the left subtree and right subtree in sequence to finally obtain all root-to-leaf paths.

Method 2: Iterative DFS (Simulating recursion with a Stack)

We can use a stack to simulate the DFS process, avoiding recursive calls.

• Initialize the stack. The elements are tuples of (current node, current path string);
• Each time, pop a node and its path from the stack:
• If it is a leaf node, add the path to the result set;
• Otherwise, sequentially push its right child node and left child node onto the stack, and append the path string;
• Since the stack follows a Last-In-First-Out (LIFO) structure, and we want to maintain a "left then right" traversal order, the right child node goes to the stack before the left child node.

Implementation

python

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        # ============ Iterative approach ================ #
        if not root:
            return []

        res = []  # Store all path results
        stack = [(root, str(root.val))]  # Initial stack: node + current path string

        while stack:
            node, path = stack.pop()

            # If it is a leaf node, append to the results list
            if not node.left and not node.right:
                res.append(path)

            # Note: Push the right subtree first, then push the left subtree, so the left subtree is processed first (simulating the recursion order)
            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

        # ============ Recursive approach ================ #

        ans = []  # Used to store all path results
        path = []  # Temporary path recording

        def dfs(node):
            if not node:
                return  # Return directly when encountering an empty node
            
            # Add the current node's value to the path (convert to string)
            path.append(str(node.val))

            # If it is a leaf node, construct the path string and add it to the result
            if not node.left and not node.right:
                ans.append('->'.join(path))

            # Continue recursing through the left and right subtrees
            dfs(node.left)
            dfs(node.right)

            # Backtracking: Reverse the modification to the path made by this recursion
            path.pop()
        
        # Start DFS from the root node
        dfs(root)

        return ans

javascript

/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function(root) {
    // ======= Iterative approach =====

    // Store all path results
    const ans = [];
    if (!root) return ans;
    // Initial stack: node + current path string
    const stack = [[root, String(root.val)]];

    while (stack.length) {
        const [node, path] = stack.pop();

        // If it is a leaf node, append to the results list
        if (!node.left && !node.right) 
            ans.push(path);

        // Note: Push the right subtree first, then push the left subtree, so the left subtree is processed first (simulating the recursion order)
        if (node.right) 
            stack.push([node.right, path + '->' + String(node.right.val)]);

        if (node.left) 
            stack.push([node.left, path + '->' + String(node.left.val)])
    }

    return ans;

    // ======= Recursive approach =======

    /*
    // Used to store all path results
    const ans = [];
    // Temporary path recording
    const path = [];

    function dfs(node) {
        // Return directly when encountering an empty node
        if (!node) return;

        // Add the current node's value to the path
        path.push(node.val);

        // If it is a leaf node, construct the path string and add it to the result
        if (!node.left && !node.right) 
            ans.push(path.join('->'));

        // Continue recursing through the left and right subtrees
        dfs(node.left)
        dfs(node.right)

        // Backtracking: Reverse the modification to the path made by this recursion
        path.pop();
    }

    // Start DFS from the root node
    dfs(root)
    return ans;
    */
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Links

257. Binary Tree Paths (English)

257. 二叉树的所有路径 (Chinese)