257. 二叉树的所有路径

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

class Solution {
private:
    void traversal(TreeNode* cur, string path, vector<string>& res)
    {
        path += std::to_string(cur->val);
        if(cur->left==nullptr && cur->right==nullptr)
        {
            res.push_back(path);
            return;
        }
        if(cur->left) traversal(cur->left,path+"->",res);
        if(cur->right) traversal(cur->right,path+"->",res);
    }
public:
    //这道题所使用的回溯，即进入子节点 退出之后不改变在该节点path的值
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        string path;
        if(root == nullptr) return res;
        traversal(root,path,res);
        return res;
    }
    vector<string> binaryTreePaths1(TreeNode* root) {
        vector<string> res;
        stack<TreeNode*> sta1;
        stack<string> sta2;
        if(root == nullptr) return res;
        sta1.push(root);
        sta2.push(std::to_string(root->val));
        while(!sta1.empty())
        {
            TreeNode *node = sta1.top(); sta1.pop();
            string path = sta2.top(); sta2.pop();
            if(node->left == nullptr&&node->right == nullptr)
            {
                res.push_back(path);
            }
            if(node->right) {
                sta1.push(node->right);
                sta2.push(path + "->" + std::to_string(node->right->val));
            }
            if(node->left) {
                sta1.push(node->left);
                sta2.push(path + "->" + std::to_string(node->left->val));
            }
        }
        return res;
};