257. Binary Tree Paths257. Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

Input:    1  /   \ 2     3  \   5 Output: ["1->2->5", "1->3"] Explanation: All root-to-leaf paths are: 1->2->5, 1->3257. Binary Tree Paths

---

本题要求输出二叉树从根到叶子的所有路径，DFS题都做烂了，完整代码如下，不解释。

class Solution {
public:
    void dfs(vector<string>& ans, string cand, TreeNode* root)
    {
        cand += "->" + to_string(root->val);
        if (root->left == NULL && root->right == NULL) {
            ans.push_back(cand.substr(2));
            return;
        }
        if (root->left != NULL)
            dfs(ans, cand, root->left);
        if (root->right != NULL)
            dfs(ans, cand, root->right);
    }
    vector<string> binaryTreePaths(TreeNode* root)
    {
        vector<string> ans;
        if (root == NULL)
            return ans;
        dfs(ans, "", root);
        return ans;
    }
};

本代码提交AC，用时3MS。