二叉树的所有路径

题目：

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

思路1：

使用先序遍历把经过的节点都保存下来，遇到叶子节点则保存该路径。

class Solution {
public:
    void PreOder(TreeNode* node, string s, vector<string>& res)
    {
        if(NULL == node)
        {
            return;
        }
        s += "->"; s += to_string(node->val);
        if(NULL == node->left && NULL == node->right)
        {
            s.erase(0, 1);
            res.emplace_back(s);
            return;
        }
        PreOder(node->left, s, res);
        PreOder(node->right, s, res);
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        string s = "";
        PreOder(root, s, res);
        return res;
    }
};

思路2：

使用迭代法，使用栈保存每个访问的节点，并使用字符串s保存该路径，当遇到叶子节点时保存s；当栈中弹出栈顶元素时，s也删除最后一个元素，直至栈为空。

方法1：

class Solution {
public:
    void PreOder(TreeNode* root, vector<string>& res)
    {
        stack<TreeNode*> st;
        TreeNode* node = root;
        string s = ""; 
        while(!st.empty() || node != NULL)
        {
            while(node)
            {
                if(node != root)
                {
                    s += "->";
                }
                s += to_string(node->val);
                st.emplace(node);
                node = node->left;
            }
            node = st.top()->right;
            if(NULL == st.top()->left && NULL == st.top()->right)
            {
                res.emplace_back(s);

            }
            else if(NULL != st.top()->left && NULL != st.top()->right)
            {
                string tmp = to_string(st.top()->val) + "->" + to_string(st.top()->left->val);  //一定要加左孩子的值
                size_t index = s.rfind(tmp);      //一定要使用rfind
                if(index != string::npos)
                {
                    s.erase(index + to_string(st.top()->val).length(), string::npos);
                }
            }
            st.pop();
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        if(NULL == root)
        {
            return res;
        }
        PreOder(root, res);
        return res;
    }
};//写了一天的迭代法

方法2：

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        if(NULL == root)
        {
            return res;
        }
        stack<TreeNode*> tree_st;
        stack<string> path_st;
        tree_st.emplace(root);
        path_st.emplace(to_string(root->val));
        while(!tree_st.empty())
        {
            TreeNode* node = tree_st.top(); tree_st.pop()
            string path = path_st.top(); path_st.pop();

            if(NULL == node->right && NULL == node->right)   
            {
                res.emplace_back(path);
            }

            if(node->right)
            {
                tree_st.emplace_back(node->right);
                path += "->"; path += to_string(node->right->val);
            }

            if(node->left)
            {
                tree_st.emplace_back(node->left);
                path += "->"; path += to_string(node->left->val);
            }
        }
        return res;
    }
};