[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;
            }
        };

Log in to reply
 

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