二叉树的所有路径

1.使用DFS

当遇到子叶节点时，此条路径结束，加入到Paths数组中

DFS 深度优先搜索
递归DFS：

class Solution {
public:
    void construct_paths(TreeNode* root, string path, vector<string>& paths) {
        if (root != nullptr) {
            path += to_string(root->val);
            if (root->left == nullptr && root->right == nullptr) {  // 当前节点是叶子节点 
                paths.push_back(path);                              // 把路径加入到答案中
            } else {
                path += "->";  // 当前节点不是叶子节点，继续递归遍历
                construct_paths(root->left, path, paths);
                construct_paths(root->right, path, paths);
            }
        }
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> paths;
        construct_paths(root, "", paths);
        return paths;
    }
};

非递归DFS

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> vec;
        stack<TreeNode*> stkin;
        stack<TreeNode*> stkout;
        stkin.push(root);
        set<TreeNode*> visited;
        while(!stkin.empty())
        {
            TreeNode* cur = stkin.top();
            if(cur->left != nullptr && visited.count(cur->left) == 0) {stkin.push(cur->left); continue;}  //左右节点加入栈中
            if(cur->right != nullptr && visited.count(cur->right) == 0) {stkin.push(cur->right); continue;}
            if(cur->left == nullptr && cur->right == nullptr) //遇到子叶节点开始处理路径  处理路径的方法使用双栈输出
            {
                while(!stkin.empty())
                {
                    TreeNode* cur1 = stkin.top();
                    stkout.push(cur1);
                    stkin.pop();
                }
                string str;
                while(!stkout.empty())
                {
                    TreeNode* cur1 = stkout.top();
                    string val = to_string (cur1->val);
                    stkin.push(cur1);
                    stkout.pop();
                    str = str + val + "->";
                }
                str.erase(str.end()-1);
                str.erase(str.end()-1);
                vec.push_back(str);
            }
            visited.insert(cur);          
             stkin.pop();      //通过pop()回溯到“根节点” 
        }
            return vec;
    }
};

2.使用DFS，利用队列进行处理

每次处理node.top 和 path.top 两个元素，node.top处理后加入他的左右两个子节点， path.top处理后加入 node.top的左右节点。

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> paths;
        if (root == nullptr) {
            return paths;
        }
        queue<TreeNode*> node_queue;
        queue<string> path_queue;

        node_queue.push(root);
        path_queue.push(to_string(root->val));

        while (!node_queue.empty()) {              //DFS队列循环
            TreeNode* node = node_queue.front(); 
            string path = path_queue.front();
            node_queue.pop();
            path_queue.pop();

            if (node->left == nullptr && node->right == nullptr) {  //判断路径是否结束
                paths.push_back(path);
            } else {
                if (node->left != nullptr) {
                    node_queue.push(node->left);
                    path_queue.push(path + "->" + to_string(node->left->val));   
                }

                if (node->right != nullptr) {
                    node_queue.push(node->right);
                    path_queue.push(path + "->" + to_string(node->right->val));
                }
            }
        }
        return paths;
    }
};

https://leetcode-cn.com/problems/binary-tree-paths/