LeetCode 257. 二叉樹所有根到葉子路徑：遞歸回溯解法（Java）

題目：給定二叉樹，返回所有從根節點到葉子節點的路徑。路徑格式如 "1->2->5"。例如輸入 [1,2,3,null,5]，輸出 ["1->2->5","1->3"]。

遞歸回溯思路

1. 深度優先遍歷，維護當前路徑 List path。
2. 進入節點時 path.add(node.val)。
3. 若為葉子節點（left==null && right==null），將路徑轉字符串加入結果集。
4. 遞歸左右子樹時傳遞 new ArrayList(path) 副本，自動實現回溯（無需手動 remove）。
5. 返回結果 List。

Java 實現

class Solution {
    public List binaryTreePaths(TreeNode root) {
        List result = new ArrayList<>();
        if (root == null) return result;
        dfs(root, new ArrayList<>(), result);
        return result;
    }

    private void dfs(TreeNode node, List path, List result) {
        if (node == null) return;
        path.add(node.val);
        if (node.left == null && node.right == null) {
            result.add(pathToString(path));
            return;
        }
        if (node.left != null) dfs(node.left, new ArrayList<>(path), result);
        if (node.right != null) dfs(node.right, new ArrayList<>(path), result);
    }

    private String pathToString(List path) {
        StringBuilder sb = new StringBuilder();
        sb.append(path.get(0));
        for (int i = 1; i < path.size(); i++) sb.append("->").append(path.get(i));
        return sb.toString();
    }
}

複雜度分析

• 時間：O(N)，每個節點訪問一次，路徑複製總長度 O(N)（每條邊被複製常數次）。
• 空間：O(H) 遞歸棧 + O(N) 結果存儲，H 為樹高。

優化方向

• 使用單一 List + 手動 add/remove 回溯，避免創建大量 ArrayList 副本（空間優化）。
• 迭代法（顯式棧）避免遞歸棧溢出風險。