2023.7.5
? ? ? ? ?這題需要用到遞歸+回溯，也是我第一次接觸回溯這個(gè)概念。?
? ? ? ? 大致思路是：
????????在reversal函數(shù)中，首先將當(dāng)前節(jié)點(diǎn)的值加入到路徑path中。然后判斷當(dāng)前節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)，即沒有左右子節(jié)點(diǎn)。如果是葉子節(jié)點(diǎn)，將路徑轉(zhuǎn)化為字符串并保存到result中。
????????接下來，分別遞歸處理當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。遞歸調(diào)用reversal函數(shù)時(shí)，將左子節(jié)點(diǎn)或右子節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn)，并傳遞更新后的路徑path和result。在遞歸調(diào)用之后，需要進(jìn)行回溯操作，即將剛添加的節(jié)點(diǎn)值從路徑path中移除，以保證在遍歷其他路徑時(shí)路徑的正確性。
? ? ? ??總體而言，通過遞歸的深度優(yōu)先搜索算法，遍歷了給定二叉樹的所有路徑，并將路徑保存在一個(gè)字符串的向量中。 下面上代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-521928.html
class Solution {
public:
void reversal(TreeNode* cur, vector<int>& path, vector<string>& result)
{
path.push_back(cur->val);
if(cur->left==nullptr && cur->right==nullptr) //葉子節(jié)點(diǎn) 將路徑保存
{
string spath;
for(int i=0; i<path.size()-1; i++)
{
spath += to_string(path[i]); //需要將數(shù)組的整型值->字符串型值
spath += "->";
}
spath += to_string(path[path.size()-1]);
result.push_back(spath);
}
if(cur->left)
{
reversal(cur->left,path,result);
path.pop_back();//回溯
}
if(cur->right)
{
reversal(cur->right,path,result);
path.pop_back();//回溯
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
vector<int> path;
reversal(root, path, result);
return result;
}
};? ? ? ? 需要注意reversal函數(shù)傳遞參數(shù)的兩個(gè)vector 需要加&符號(hào)，以保證是在原vector上修改。文章來源地址http://www.zghlxwxcb.cn/news/detail-521928.html
到了這里，關(guān)于leetcode 257. 二叉樹的所有路徑的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
