Recursive and non-recursive C++ implementation


  • 0
    X
    class Solution {
    public:
        vector<string> binaryTreePaths(TreeNode* root) {
            vector<int> path;
            vector<string> paths;
            
            if (root != nullptr)
                preDfs(root, path, paths);
            
            return paths;
        }
        
    private:
        void preDfs(const TreeNode *node, vector<int> &path, vector<string> &pathVector) {
            path.push_back(node->val);
            if (node->left == nullptr && node->right == nullptr) {
                string pathStr(to_string(*path.begin()));
                for_each(path.begin()+1, path.end(), [&](int val) {pathStr.append("->" + to_string(val));});             
                pathVector.push_back(pathStr);
                return;
            }
            
            if (node->left != nullptr) {
                preDfs(node->left, path, pathVector);
                path.pop_back();
            }          
            if (node->right != nullptr) {
                preDfs(node->right, path, pathVector);
                path.pop_back();
            } 
        }        
    };
    

    class Solution {
    public:
        vector<string> binaryTreePaths(TreeNode* root) {
            vector<int> path;
            vector<string> paths;
            stack<pair<TreeNode *, int>> nodesUnexplored; //the second item indicates which level the node is at
            
            if (root != nullptr)
                nodesUnexplored.push(make_pair(root,0));
            
            while (!nodesUnexplored.empty()) {
                auto currNode = nodesUnexplored.top();
                nodesUnexplored.pop();
                
                while (currNode.second < path.size())
                    path.pop_back();
                path.push_back(currNode.first->val);
                
                if (currNode.first->left == nullptr && currNode.first->right == nullptr) {
                    string pathStr(to_string(path[0]));
                    for_each(path.begin()+1, path.end(), [&](int val) {pathStr.append("->" + to_string(val));});
                    paths.push_back(pathStr);
                }
                else {
                    if (currNode.first->right != nullptr)
                        nodesUnexplored.push(make_pair(currNode.first->right, currNode.second+1));
                    if (currNode.first->left != nullptr)
                        nodesUnexplored.push(make_pair(currNode.first->left, currNode.second+1));
                }
            }
            
            return paths;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.