DFS


  • 0
    B
    public:
        void dfs(TreeNode* start, vector<TreeNode*> uptostart, vector<vector<TreeNode*> >& finalresults)
        {
            if (!start->left && !start->right) { finalresults.push_back(uptostart); return; }
            bool vectorchanged = false;
            if (start->left) { 
                uptostart.push_back(start->left); 
                vectorchanged=true;
                dfs(start->left, uptostart, finalresults); 
                }
            if (start->right){ 
                if (vectorchanged) 
                  uptostart.back() = start->right; 
                else 
                  uptostart.push_back(start->right);
                dfs(start->right, uptostart, finalresults);
                }
        }
        
        vector<string> binaryTreePaths(TreeNode* root) {
            vector<string> result;
            if (!root) return result;
            vector<vector<TreeNode*> > finalresults;
            vector<TreeNode*> uptostart; uptostart.push_back(root);
            dfs(root,uptostart,finalresults);
            for (vector<TreeNode*>& x : finalresults)
              {
                  string s;
                  bool begin = true;
                  for (TreeNode* y : x)
                    {
                        s += (begin) ? "" : "->";
                        if (begin) begin = false;
                        s += to_string(y->val);
                    }
                  result.push_back(s);
              }
            return result;
        }
    };

Log in to reply
 

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