[[415834]]

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

二叉樹(shù)的所有路徑

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

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

說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

示例:

思路

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

在這道題目中將第一次涉及到回溯，因?yàn)槲覀円崖窂接涗浵聛?lái)，需要回溯來(lái)回退一一個(gè)路徑在進(jìn)入另一個(gè)路徑。

前序遍歷以及回溯的過(guò)程如圖：

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

遞歸

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

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

void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) 

2.確定遞歸終止條件

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

if (cur == NULL) { 
    終止處理邏輯 
} 

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

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

所以本題的終止條件是：

if (cur->left == NULL && cur->right == NULL) { 
    終止處理邏輯 
} 

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

再來(lái)看一下終止處理的邏輯。

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

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

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

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

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

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]); // 記錄最后一個(gè)節(jié)點(diǎn)（葉子節(jié)點(diǎn)） 
    result.push_back(sPath); // 收集一個(gè)路徑 
    return; 
} 

3.確定單層遞歸邏輯

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

path.push_back(cur->val); 

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

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

if (cur->left) { 
    traversal(cur->left, path, result); 
} 
if (cur->right) { 
    traversal(cur->right, path, result); 
} 

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

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

if (cur->left) { 
    traversal(cur->left, path, result); 
} 
if (cur->right) { 
    traversal(cur->right, path, result); 
} 
path.pop_back(); 

這個(gè)回溯就要很大的問(wèn)題，我們知道，回溯和遞歸是一一對(duì)應(yīng)的，有一個(gè)遞歸，就要有一個(gè)回溯，這么寫(xiě)的話(huà)相當(dāng)于把遞歸和回溯拆開(kāi)了， 一個(gè)在花括號(hào)里，一個(gè)在花括號(hào)外。

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

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

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)了回溯。

那么如上代碼可以精簡(jiǎ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; 
 
    } 
}; 

如上代碼精簡(jiǎn)了不少，也隱藏了不少東西。

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

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

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

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); // 右 
} 

此時(shí)就沒(méi)有回溯了，這個(gè)代碼就是通過(guò)不了的了。

如果想把回溯加上，就要 在上面代碼的基礎(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)該可以感受出來(lái)，如果把 path + "->"作為函數(shù)參數(shù)就是可以的，因?yàn)椴⒂袥](méi)有改變path的數(shù)值，執(zhí)行完遞歸函數(shù)之后，path依然是之前的數(shù)值(相當(dāng)于回溯了)

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

迭代法

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

這里除了模擬遞歸需要一個(gè)棧，同時(shí)還需要一個(gè)棧來(lái)存放對(duì)應(yīng)的遍歷路徑。

C++代碼如下：

class Solution { 
public: 
    vector<string> binaryTreePaths(TreeNode* root) { 
        stack<TreeNode*> treeSt;// 保存樹(shù)的遍歷節(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)對(duì)應(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é)，可以直接定義一個(gè)成員變量為object的棧Stack stack = new Stack<>();，這樣就不用定義兩個(gè)棧了，都放到一個(gè)棧里就可以了。

總結(jié)

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

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

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

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

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

其他語(yǔ)言版本

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 
}