以為只用了遞歸，其實(shí)還用了回溯

257. 二叉樹的所有路徑

題目地址：https://leetcode-cn.com/problems/binary-tree-paths/

給定一個二叉樹，返回所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑。

說明： 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。

思路

這道題目要求從根節(jié)點(diǎn)到葉子的路徑，所以需要前序遍歷，這樣才方便讓父節(jié)點(diǎn)指向孩子節(jié)點(diǎn)，找到對應(yīng)的路徑。

在這道題目中將第一次涉及到回溯，因?yàn)槲覀円崖窂接涗浵聛恚枰厮輥砘赝艘灰粋€路徑在進(jìn)入另一個路徑。

前序遍歷以及回溯的過程如圖：

我們先使用遞歸的方式，來做前序遍歷。要知道遞歸和回溯就是一家的，本題也需要回溯。

遞歸

遞歸函數(shù)函數(shù)參數(shù)以及返回值

要傳入根節(jié)點(diǎn)，記錄每一條路徑的path，和存放結(jié)果集的result，這里遞歸不需要返回值，代碼如下：

void traversal（TreeNode* cur， vector《int》& path， vector《string》& result）

確定遞歸終止條件

再寫遞歸的時候都習(xí)慣了這么寫：

if （cur == NULL） {

終止處理邏輯

}

但是本題的終止條件這樣寫會很麻煩，因?yàn)楸绢}要找到葉子節(jié)點(diǎn)，就開始結(jié)束的處理邏輯了（把路徑放進(jìn)result里）。

那么什么時候算是找到了葉子節(jié)點(diǎn)？ 是當(dāng) cur不為空，其左右孩子都為空的時候，就找到葉子節(jié)點(diǎn)。

所以本題的終止條件是：

if （cur-》left == NULL && cur-》right == NULL） {

終止處理邏輯

}

為什么沒有判斷cur是否為空呢，因?yàn)橄旅娴倪壿嬁梢钥刂瓶展?jié)點(diǎn)不入循環(huán)。

再來看一下終止處理的邏輯。

這里使用vector結(jié)構(gòu)path來記錄路徑，所以要把vector結(jié)構(gòu)的path轉(zhuǎn)為string格式，在把這個string 放進(jìn) result里。

那么為什么使用了vector結(jié)構(gòu)來記錄路徑呢？ 因?yàn)樵谙旅嫣幚韱螌舆f歸邏輯的時候，要做回溯，使用vector方便來做回溯。

可能有的同學(xué)問了，我看有些人的代碼也沒有回溯啊。

其實(shí)是有回溯的，只不過隱藏在函數(shù)調(diào)用時的參數(shù)賦值里，下文我還會提到。

這里我們先使用vector結(jié)構(gòu)的path容器來記錄路徑，那么終止處理邏輯如下：

if （cur-》left == NULL && cur-》right == NULL） { // 遇到葉子節(jié)點(diǎn)

string sPath;

for （int i = 0; i 《 path.size（） - 1; i++） { // 將path里記錄的路徑轉(zhuǎn)為string格式

sPath += to_string（path［i］）;

sPath += “-》”;

}

sPath += to_string（path［path.size（） - 1］）; // 記錄最后一個節(jié)點(diǎn)（葉子節(jié)點(diǎn)）

result.push_back（sPath）; // 收集一個路徑

return;

}

確定單層遞歸邏輯

因?yàn)槭乔靶虮闅v，需要先處理中間節(jié)點(diǎn)，中間節(jié)點(diǎn)就是我們要記錄路徑上的節(jié)點(diǎn)，先放進(jìn)path中。

path.push_back（cur-》val）;

然后是遞歸和回溯的過程，上面說過沒有判斷cur是否為空，那么在這里遞歸的時候，如果為空就不進(jìn)行下一層遞歸了。

所以遞歸前要加上判斷語句，下面要遞歸的節(jié)點(diǎn)是否為空，如下

if （cur-》left） {

traversal（cur-》left， path， result）;

}

if （cur-》right） {

traversal（cur-》right， path， result）;

}

此時還沒完，遞歸完，要做回溯啊，因?yàn)閜ath 不能一直加入節(jié)點(diǎn)，它還要刪節(jié)點(diǎn)，然后才能加入新的節(jié)點(diǎn)。

那么回溯要怎么回溯呢，一些同學(xué)會這么寫，如下：

if （cur-》left） {

traversal（cur-》left， path， result）;

}

if （cur-》right） {

traversal（cur-》right， path， result）;

}

path.pop_back（）;

這個回溯就要很大的問題，我們知道，回溯和遞歸是一一對應(yīng)的，有一個遞歸，就要有一個回溯，這么寫的話相當(dāng)于把遞歸和回溯拆開了， 一個在花括號里，一個在花括號外。

所以回溯要和遞歸永遠(yuǎn)在一起，世界上最遙遠(yuǎn)的距離是你在花括號里，而我在花括號外！

那么代碼應(yīng)該這么寫：

if （cur-》left） {

traversal（cur-》left， path， result）;

path.pop_back（）; // 回溯

}

if （cur-》right） {

traversal（cur-》right， path， result）;

path.pop_back（）; // 回溯

}

那么本題整體代碼如下：

class Solution {private：

void traversal（TreeNode* cur， vector《int》& path， vector《string》& result） {

path.push_back（cur-》val）;

// 這才到了葉子節(jié)點(diǎn)

if （cur-》left == NULL && cur-》right == NULL） {

string sPath;

for （int i = 0; i 《 path.size（） - 1; i++） {

sPath += to_string（path［i］）;

sPath += “-》”;

}

sPath += to_string（path［path.size（） - 1］）;

result.push_back（sPath）;

return;

}

if （cur-》left） {

traversal（cur-》left， path， result）;

path.pop_back（）; // 回溯

}

if （cur-》right） {

traversal（cur-》right， path， result）;

path.pop_back（）; // 回溯

}

}

public：

vector《string》 binaryTreePaths（TreeNode* root） {

vector《string》 result;

vector《int》 path;

if （root == NULL） return result;

traversal（root， path， result）;

return result;

}

};

如上的C++代碼充分體現(xiàn)了回溯。

那么如上代碼可以精簡成如下代碼：

class Solution {private：

void traversal（TreeNode* cur， string path， vector《string》& result） {

path += to_string（cur-》val）; // 中

if （cur-》left == NULL && cur-》right == NULL） {

result.push_back（path）;

return;

}

if （cur-》left） traversal（cur-》left， path + “-》”， result）; // 左

if （cur-》right） traversal（cur-》right， path + “-》”， result）; // 右

}

public：

vector《string》 binaryTreePaths（TreeNode* root） {

vector《string》 result;

string path;

if （root == NULL） return result;

traversal（root， path， result）;

return result;

}

};

如上代碼精簡了不少，也隱藏了不少東西。

注意在函數(shù)定義的時候void traversal（TreeNode* cur， string path， vector《string》& result） ，定義的是string path，每次都是復(fù)制賦值，不用使用引用，否則就無法做到回溯的效果。

那么在如上代碼中，貌似沒有看到回溯的邏輯，其實(shí)不然，回溯就隱藏在traversal（cur-》left， path + “-》”， result）;中的 path + “-》”。 每次函數(shù)調(diào)用完，path依然是沒有加上“-》” 的，這就是回溯了。

為了把這份精簡代碼的回溯過程展現(xiàn)出來，大家可以試一試把：

if （cur-》left） traversal（cur-》left， path + “-》”， result）; // 左 回溯就隱藏在這里

改成如下代碼：

path += “-》”;

traversal（cur-》left， path， result）; // 左

即：

if （cur-》left） {

path += “-》”;

traversal（cur-》left， path， result）; // 左

}

if （cur-》right） {

path += “-》”;

traversal（cur-》right， path， result）; // 右

}

此時就沒有回溯了，這個代碼就是通過不了的了。

如果想把回溯加上，就要 在上面代碼的基礎(chǔ)上，加上回溯，就可以AC了。

if （cur-》left） {

path += “-》”;

traversal（cur-》left， path， result）; // 左

path.pop_back（）; // 回溯

path.pop_back（）;

}

if （cur-》right） {

path += “-》”;

traversal（cur-》right， path， result）; // 右

path.pop_back（）; // 回溯

path.pop_back（）;

}

大家應(yīng)該可以感受出來，如果把 path + “-》”作為函數(shù)參數(shù)就是可以的，因?yàn)椴⒂袥]有改變path的數(shù)值，執(zhí)行完遞歸函數(shù)之后，path依然是之前的數(shù)值（相當(dāng)于回溯了）

綜合以上，第二種遞歸的代碼雖然精簡但把很多重要的點(diǎn)隱藏在了代碼細(xì)節(jié)里，第一種遞歸寫法雖然代碼多一些，但是把每一個邏輯處理都完整的展現(xiàn)了出來了。

迭代法

至于非遞歸的方式，我們可以依然可以使用前序遍歷的迭代方式來模擬遍歷路徑的過程，對該迭代方式不了解的同學(xué)，可以看文章二叉樹：聽說遞歸能做的，棧也能做！和二叉樹：前中后序迭代方式統(tǒng)一寫法。

這里除了模擬遞歸需要一個棧，同時還需要一個棧來存放對應(yīng)的遍歷路徑。

C++代碼如下：

class Solution {public：

vector《string》 binaryTreePaths（TreeNode* root） {

stack《TreeNode*》 treeSt;// 保存樹的遍歷節(jié)點(diǎn)

stack《string》 pathSt; // 保存遍歷路徑的節(jié)點(diǎn)

vector《string》 result; // 保存最終路徑集合

if （root == NULL） return result;

treeSt.push（root）;

pathSt.push（to_string（root-》val））;

while （！treeSt.empty（）） {

TreeNode* node = treeSt.top（）; treeSt.pop（）; // 取出節(jié)點(diǎn) 中

string path = pathSt.top（）;pathSt.pop（）; // 取出該節(jié)點(diǎn)對應(yīng)的路徑

if （node-》left == NULL && node-》right == NULL） { // 遇到葉子節(jié)點(diǎn)

result.push_back（path）;

}

if （node-》right） { // 右

treeSt.push（node-》right）;

pathSt.push（path + “-》” + to_string（node-》right-》val））;

}

if （node-》left） { // 左

treeSt.push（node-》left）;

pathSt.push（path + “-》” + to_string（node-》left-》val））;

}

}

return result;

}

};

當(dāng)然，使用java的同學(xué)，可以直接定義一個成員變量為object的棧Stack《Object》 stack = new Stack《》（）;，這樣就不用定義兩個棧了，都放到一個棧里就可以了。

總結(jié)

本文我們開始初步涉及到了回溯，很多同學(xué)過了這道題目，可能都不知道自己其實(shí)使用了回溯，回溯和遞歸都是相伴相生的。

我在第一版遞歸代碼中，把遞歸與回溯的細(xì)節(jié)都充分的展現(xiàn)了出來，大家可以自己感受一下。

第二版遞歸代碼對于初學(xué)者其實(shí)非常不友好，代碼看上去簡單，但是隱藏細(xì)節(jié)于無形。

最后我依然給出了迭代法。

對于本地充分了解遞歸與回溯的過程之后，有精力的同學(xué)可以在去實(shí)現(xiàn)迭代法。

其他語言版本

Java：

//解法一class Solution {

/**

* 遞歸法

*/

public List《String》 binaryTreePaths（TreeNode root） {

List《String》 res = new ArrayList《》（）;

if （root == null） {

return res;

}

List《Integer》 paths = new ArrayList《》（）;

traversal（root， paths， res）;

return res;

}

private void traversal（TreeNode root， List《Integer》 paths， List《String》 res） {

paths.add（root.val）;

// 葉子結(jié)點(diǎn)

if （root.left == null && root.right == null） {

// 輸出

StringBuilder sb = new StringBuilder（）;

for （int i = 0; i 《 paths.size（） - 1; i++） {

sb.append（paths.get（i））.append（“-》”）;

}

sb.append（paths.get（paths.size（） - 1））;

res.add（sb.toString（））;

return;

}

if （root.left ！= null） {

traversal（root.left， paths， res）;

paths.remove（paths.size（） - 1）;// 回溯

}

if （root.right ！= null） {

traversal（root.right， paths， res）;

paths.remove（paths.size（） - 1）;// 回溯

}

}

}

Python：

class Solution：

def binaryTreePaths（self， root： TreeNode） -》 List［str］：

path=［］

res=［］

def backtrace（root， path）：

if not root:return

path.append（root.val）

if （not root.left）and （not root.right）：

res.append（path［：］）

ways=［］

if root.left:ways.append（root.left）

if root.right:ways.append（root.right）

for way in ways：

backtrace（way，path）

path.pop（）

backtrace（root，path）

return ［“-》”.join（list（map（str，i））） for i in res］

Go：

func binaryTreePaths（root *TreeNode） ［］string {

res ：= make（［］string， 0）

var travel func（node *TreeNode， s string）

travel = func（node *TreeNode， s string） {

if node.Left == nil && node.Right == nil {

v ：= s + strconv.Itoa（node.Val）

res = append（res， v）

return

}

s = s + strconv.Itoa（node.Val） + “-》”

if node.Left ！= nil {

travel（node.Left， s）

}

if node.Right ！= nil {

travel（node.Right， s）

}

}

travel（root， “”）

return res

}

責(zé)任編輯：haq