Leetcode 257. 二叉樹的所有路徑

　　對二叉樹的操作，很多情況都是基于其周遊操作進行的，是以，二叉樹的周遊操作應熟記于心！　

　　題目是說将二叉樹的所有路徑輸出，輸出形式有特定的要求，簡單的周遊操作即可完成任務！

　　這裡，單獨寫了一個函數，用于将數組中的int類型，存至一個 vector<string> 類型的結果集中，void storeRes(vector<int> vc,vector<string> &res)，int類型轉換成string類型，最簡單的方法是使用C++11标準的to_string()函數，代碼如下：

1 void storeRes(vector<int> vc,vector<string> &res){
 2         //函數功能：将vc中int類型的數字連接配接成字元串，存入res中
 3         string s="";
 4         for(int i=0;i<vc.size();i++)
 5         {
 6             if(i==vc.size()-1)
 7                 s+=(to_string(vc[i])+"");
 8             else
 9                 s+=(to_string(vc[i])+"->");
10         }
11         //cout<<"string s is "<<s<<endl;
12         res.push_back(s);
13     }

　　這裡我們使用函數的結果要改變最後的結果res，是以采用了引用類型的參數！

　　基本思路是每次通路到葉子節點的時候，将已有的路徑進行輸出，可以用一個棧來存儲，每次回溯的時候，節點出棧，然後通路至葉子節點時，對棧結構進行周遊即可，這裡采用vector進行操作，其優勢在于，可以直接采用下标進行通路！

　　筆記：

　　　　vector結構删除末尾元素的三種方法pop_back(),erase()和remove函數

向量容器的成員函數pop_back()可以删除最後一個元素，而函數erase()可以删除由一個iterator指出的元素，也可以删除一個指定範圍的元素。
還可以采用通用算法remove()來删除vector容器中的元素，不同的是，采用remove一般情況下不會改變容器的大小，而pop_back()與erase()等成員函數會改變容器的大小。
另外，疊代器用于erase删除元素後，其後會失效，即不能再用該疊代器操作向量。

代碼如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        if(root==nullptr)
            return res;
        //周遊，直到葉子節點
        vector<int> a;
        dfs(root,a);
        return res;
    }

    void dfs(TreeNode* root,vector<int> &a)
    {
        if(root==nullptr)
            return;
        //cout<<root->val<<endl;
        a.push_back(root->val);
        if(root->left!=nullptr)
            dfs(root->left,a);
        if(root->right!=nullptr)
            dfs(root->right,a);
        //此時為葉子節點
        if(root->left==nullptr && root->right==nullptr)
        {
            storeRes(a,res);
        }
        a.pop_back();  //彈出一個元素
        return;
    }

    void storeRes(vector<int> vc,vector<string> &res){
        //函數功能：将vc中int類型的數字連接配接成字元串，存入res中
        string s="";
        for(int i=0;i<vc.size();i++)
        {
            if(i==vc.size()-1)
                s+=(to_string(vc[i])+"");
            else
                s+=(to_string(vc[i])+"->");
        }
        //cout<<"string s is "<<s<<endl;
        res.push_back(s);
    }
private:
    vector<string> res;
};