4ms C++ two methods: recursive and iterative solutions


  • 0
    H

    recursive methods is easy to finish.

    class Solution {
    public:

    void helper(TreeNode*node, vector<string>& res, string output){

      if(node == NULL) return;
      
      if(node->left == NULL && node->right == NULL){
          output += to_string(node->val);
          res.push_back(output);
          return;
      }
      
      output +=  to_string(node->val) + "->";
      
      if(node->left){
          helper(node->left,res,output);
      }
      
      if(node->right){
          helper(node->right,res,output);
      }
    

    }

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        if(root == NULL) return res;
        
        string output;
        
        TreeNode* node = root;
        
        helper(node,res,output);
        
        return res;
    }
    

    };

    =================================

    For the iterative, it is not as intuitive. Here I use a vector<TreeNode*> to store all the nodes in one path, and check the last node of this vector, if the last node is an leaf node, then we construct the string of the values in this path. The idea is to use a queue to store all the possible paths ( using vector for each path)

    class Solution {
    public:
    vector<string> binaryTreePaths(TreeNode* root) {

        vector<string> res;
        if(root == NULL) return res;
        queue<vector<TreeNode*>> q;
        
        vector<TreeNode*> cur;
        cur.push_back(root);
        q.push(cur);
        
        while(!q.empty()){
            
            int qsize = q.size();
            
            for(int i = 0; i<qsize; i++){
                cur = q.front();
                q.pop();
                
                TreeNode* last = cur[cur.size()-1];
                
                if(last->left != NULL && last->right ==NULL){
                    
                    cur.push_back(last->left);
                    q.push(cur);
                    
                }else  if(last->left == NULL && last->right !=NULL){
                    cur.push_back(last->right);
                    q.push(cur);
                    
                }else if(last->left != NULL && last->right != NULL){
                    cur.push_back(last->left);
                    q.push(cur);
                    cur.pop_back();
                    cur.push_back(last->right);
                    q.push(cur);
                
                }else if(last->left == NULL && last->right == NULL){
                    
                    string output = "";
                    
                    for(int i = 0; i < cur.size(); i++){
                        
                        if(i!=cur.size()-1){
                            output += to_string(cur[i]->val) + "->";
                        }else{
                            output += to_string(cur[i]->val);
                        }
                    }
                    
                    res.push_back(output);
                }
            }
        }
        
        
        return res;
        
    }
    

    };


  • 0
    T

    Hi,

    I got a similar solution by writing a helper function as well.

    But I am wondering is there a way to do recursively without helper functions?


  • 0
    H

    please see the above, I added the recursive solution.


Log in to reply
 

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