LeetCode 257 Binary Tree Paths：DFS 收集所有根到葉路徑

題目回顧

給定二叉樹，返回所有從根到葉的路徑，格式如 "1->2->5"。
例：1 / \ 2 3 \ 5 → ["1->2->5", "1->3"]

遞歸 DFS 實現

class Solution {
public:
    vector binaryTreePaths(TreeNode* root) {
        vector res;
        if (!root) return res;
        dfs(root, to_string(root->val), res);
        return res;
    }
    
private:
    void dfs(TreeNode* node, string path, vector& res) {
        if (!node->left && !node->right) {
            res.push_back(path);
            return;
        }
        if (node->left) dfs(node->left, path + "->" + to_string(node->left->val), res);
        if (node->right) dfs(node->right, path + "->" + to_string(node->right->val), res);
    }
};

迭代法（棧）

vector binaryTreePaths(TreeNode* root) {
    vector res;
    if (!root) return res;
    stack> st;
    st.emplace(root, to_string(root->val));
    while (!st.empty()) {
        auto [node, path] = st.top(); st.pop();
        if (!node->left && !node->right) res.push_back(path);
        if (node->right) st.emplace(node->right, path + "->" + to_string(node->right->val));
        if (node->left) st.emplace(node->left, path + "->" + to_string(node->left->val));
    }
    return res;
}

複雜度

• 時間：O(n × h) 字符串拷貝開銷，n 節點數，h 樹高
• 空間：O(h) 遞歸棧/棧 + O(n × h) 結果存儲

優化：路徑用 vector 遞歸，葉節點再 join

void dfs(TreeNode* node, vector& path, vector& res) {
    path.push_back(node->val);
    if (!node->left && !node->right) {
        string s = to_string(path[0]);
        for (int i = 1; i < path.size(); ++i) s += "->" + to_string(path[i]);
        res.push_back(s);
    } else {
        if (node->left) dfs(node->left, path, res);
        if (node->right) dfs(node->right, path, res);
    }
    path.pop_back();
}