[recommend for beginners]non-recursive clean C++ implementation with detailed explanation


  • 1

    Here is my non-recursive implementation :

       class Solution {
        public:
            vector<string> binaryTreePaths(TreeNode* root) {
                vector<string> result;
                if(!root)   return result;
                
                /*** BFS : we prefer to use the deque<> structure ***/
                deque<TreeNode*> q;
                deque<string> str;
                q.push_back(root);
                str.push_back(to_string(root->val));
                /*** BFS : level-by-level-traversal ***/
                while(!q.empty()){
                    TreeNode* temp = q.front();
                    string str_temp = str.front();
                    /*** the leaf-node-path should be added to the result ***/
                    if(temp->left==NULL && temp->right==NULL) result.push_back(str_temp);
                    q.pop_front();
                    str.pop_front();
                    if(temp->left!=NULL)  {
                        q.push_back(temp->left);
                        str.push_back(str_temp+"->"+to_string(temp->left->val));
                    }
                    if(temp->right!=NULL)  {
                        q.push_back(temp->right);
                        str.push_back(str_temp+"->"+to_string(temp->right->val));
                    }
                }
                return result;
            }
        };

  • 0
    class Solution {
    public:
        vector<string> binaryTreePaths(TreeNode* root) {
            vector<string> result;
            if(!root)   return result;
            help(result, root, to_string(root->val));
            return result;
        }
        
        void help(vector<string>& result, TreeNode* root, string t){
            if(!root->left && !root->right){
                result.push_back(t);
                return;
            }
            if(root->left)  help(result, root->left, t+"->"+to_string(root->left->val));
            if(root->right) help(result, root->right, t+"->"+to_string(root->right->val));
        }
    };

Log in to reply
 

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