LeetCode刷題記錄14——257. Binary Tree Paths（easy）

目錄

前言

題目

語(yǔ)言

思路

源碼

后記

---

前言

數(shù)據(jù)結(jié)構(gòu)感覺理論簡(jiǎn)單，實(shí)踐起來(lái)很困難。

題目

給定一個(gè)二叉樹，輸出所有的根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑（以字符串的形式返回）

語(yǔ)言

C++

思路

學(xué)了數(shù)據(jù)結(jié)構(gòu)，所以一看到這種輸出路徑的，就想到了先序遍歷、中序遍歷、后序遍歷的遞歸方法。

首先寫一個(gè)方法test，這個(gè)方法就是用來(lái)遞歸求路徑的，形參有結(jié)點(diǎn)指針、字符串str和路徑paths。首先判斷結(jié)點(diǎn)指針是否為空，不為空則將這個(gè)結(jié)點(diǎn)的value加到字符串str后面，當(dāng)然，他給的是int型的value，所以得通過(guò)to_string轉(zhuǎn)化成字符串型，這樣才能不斷的加在字符串str的尾巴后面。接著分3種情況：

1. 如果結(jié)點(diǎn)的左孩子右孩子指針均為空，那么說(shuō)明他沒有孩子，則直接將str加在vector的尾部

2. 如果左孩子指針不為空，那么就遞歸調(diào)用test(root->left,str+"->",paths)

3. 如果右孩子指針不為空，那么就遞歸調(diào)用test(root->right,str+"->",paths)

最后在他所給的方法中定義個(gè)vector<string>paths，然后調(diào)用方法test(root,"",paths)，就能返回paths。

源碼

/*** 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:void test(TreeNode* root,string str,vector<string> &paths){if(root!=NULL) {str=str+to_string(root->val);if(root->left==NULL&&root->right==NULL)paths.push_back(str);if(root->left!=NULL)test(root->left,str+"->",paths);if(root->right!=NULL)test(root->right,str+"->",paths);}}vector<string> binaryTreePaths(TreeNode* root) {vector<string>paths;test(root,"",paths);return paths;}
?
};

后記

做這題我先去查了C++int型如何轉(zhuǎn)為string，然后就知道了to_string；接著考慮到?jīng)]有孩子的情況，所以又去查了如何在尾部加上數(shù)據(jù)，所以知道了push_back這個(gè)方法。

總結(jié)

以上是生活随笔為你收集整理的LeetCode刷题记录14——257. Binary Tree Paths（easy）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。