LeetCode 257 二叉树的所有路径

257.二叉树的所有路径

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

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

1.1 后序非递归实现

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) { // 经典的后序非递归实现
        vector<string> res;
        if(!root) return res;
        vector<TreeNode*> s;
        TreeNode* pre=nullptr;
        while(root||!s.empty()){
            while(root){
                s.push_back(root);
                root=root->left;
            }
            TreeNode* node=s.back();
            if(node->right&&node->right!=pre){
                root=node->right;
            }else{
                if(!node->right&&!node->left){
                    string path;
                    for(int i=0;i<s.size()-1;i++)
                        path+=(to_string(s[i]->val)+"->");
                    path+=to_string(s[s.size()-1]->val);
                    res.push_back(path);
                }
                pre=node;
                s.pop_back();
            }
        }
        return res;
    }
};

此处也可以改写为使用递归方式实现：

class Solution {
public:
    void construct_path(TreeNode* root,string path,vector<string> &res){
        if(root){
            if(!root->left&&!root->right){
                path+=to_string(root->val);
                res.push_back(path);
                return;
            }
            path+=(to_string(root->val)+"->");
            construct_path(root->left,path,res);
            construct_path(root->right,path,res);
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) { // 经典的后序非递归实现
        vector<string> res;
        if(!root) return res;
        string path;
        construct_path(root,path,res);
        return res;
    }
};

1.2 基于BFS实现

此处采取的完全是穷举的方式，创建一个路径队列，用于逐步生成全部的路径，当出栈元素是一个孩子节点时，将生成的路径加入到结果集。

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) { // 经典的后序非递归实现
        vector<string> res;
        if(!root) return res;
        queue<TreeNode*> q_node;
        queue<string> q_path;
        q_node.push(root);
        q_path.push(to_string(root->val));
        while(!q_node.empty()){
            TreeNode* node=q_node.front();
            string path=q_path.front();
            q_node.pop();
            q_path.pop();
            if(!node->left&&!node->right){
                res.push_back(path);
            }
            if(node->left){
                q_node.push(node->left);
                q_path.push(path+"->"+to_string(node->left->val));
            }
            if(node->right){
                q_node.push(node->right);
                q_path.push(path+"->"+to_string(node->right->val));
            }
        }
        return res;
    }
};