LeetCode 257 Binary Tree Paths：二叉樹根到葉路徑

題目描述

給定一棵二叉樹，返回所有從根節點到葉子節點的路徑。例如：

   1
 /   \
2     3
 \
  5

輸出：["1->2->5", "1->3"]

解題思路

本質是二叉樹的深度優先遍歷（DFS）。使用遞歸：從根節點出發，維護當前路徑字串，遇到葉子節點（左右子樹皆為空）將路徑加入結果。非遞歸亦可用堆疊實現。

Java 實現

package leetcode;
import java.util.ArrayList;
import java.util.List;
import leetcode.utils.TreeNode;

public class Binary_Tree_Paths {
    public static void main(String[] args) {
        TreeNode r = new TreeNode(1);
        TreeNode r1 = new TreeNode(2);
        TreeNode r2 = new TreeNode(3);
        TreeNode r3 = new TreeNode(5);
        r.left = r1; r.right = r2; r1.right = r3;
        System.out.println(binaryTreePaths(r));
    }

    public static List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root != null) getPath(root, String.valueOf(root.val), result);
        return result;
    }

    private static void getPath(TreeNode root, String path, List<String> result) {
        if (root.left == null && root.right == null) {
            result.add(path);
            return;
        }
        if (root.left != null) getPath(root.left, path + "->" + root.left.val, result);
        if (root.right != null) getPath(root.right, path + "->" + root.right.val, result);
    }
}

複雜度分析

• 時間複雜度：O(N)，N 為節點數，每個節點訪問一次。
• 空間複雜度：O(H)，H 為樹高，遞歸棧深度；輸出結果空間不計入。