Two 4ms clear C++ solution: iteration and recursion


  • 1
    C
        class Solution {
        public:
        	void path2str(vector<int>& path, string& spath)
        	{
        		if (path.empty())
        			return;
        		spath = spath + to_string(path[0]);
        		for (int i = 1; i < path.size(); i++)
        		{
        			spath = spath + "->";
        			spath = spath + to_string(path[i]);
        		}
        		return;
        	}
        	void binaryTreePaths_core(TreeNode* root,vector<int>& path,vector<string>& res) {
        		if (root == NULL)
        			return;
        		path.push_back(root->val);
        		if (root->left == NULL&&root->right == NULL)
        		{
        			string spath;
        			path2str(path, spath);
        			res.push_back(spath);
        		}
        		else
        		{
        			binaryTreePaths_core(root->left, path, res);
        			binaryTreePaths_core(root->right, path, res);
        		}
        		path.pop_back();
        		return;
        			
        	}
        	vector<string> binaryTreePaths(TreeNode* root) {
        		vector<string> res;
        		vector<int> path;
        		binaryTreePaths_core(root, path, res);
        		return res;
        	}
        };
    
    
    
    
    
    
    class Solution {
    public:
    	void path2str(vector<TreeNode*>& path, string& spath)
    	{
    		if (path.empty())
    			return;
    		spath = spath + to_string(path[0]->val);
    		for (int i = 1; i < path.size(); i++)
    		{
    			spath = spath + "->";
    			spath = spath + to_string(path[i]->val);
    		}
    		return;
    	}
    
    	vector<string> binaryTreePaths(TreeNode* root) {
    		vector<string> res;
    		vector<TreeNode*> path;
    		TreeNode *p = root,*plast=NULL;
    		while (p || !path.empty())
    		{
    			while (p)
    			{
    				path.push_back(p);
    				p = p->left;
    			}
    			p = path.back();
    			if (p->left == NULL&&p->right == NULL)
    			{
    				string spath;
    				path2str(path, spath);
    				res.push_back(spath);
    			}
    			if (p->right != NULL && p->right != plast)
    				p = p->right;
    			else
    			{
    				plast = p;
    				path.pop_back();
    				p = NULL;
    			}
    		}
    		return res;
    	}
    };

Log in to reply
 

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