[[415834]]

以為只用了遞歸，其實還用了回溯

二叉樹的所有路徑

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

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

說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點。

示例:

思路

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

在這道題目中將第一次涉及到回溯，因為我們要把路徑記錄下來，需要回溯來回退一一個路徑在進入另一個路徑。

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

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

遞歸

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

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

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

2.確定遞歸終止條件

再寫遞歸的時候都習慣了這么寫：

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

但是本題的終止條件這樣寫會很麻煩，因為本題要找到葉子節(jié)點，就開始結(jié)束的處理邏輯了(把路徑放進result里)。

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

所以本題的終止條件是：

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

為什么沒有判斷cur是否為空呢，因為下面的邏輯可以控制空節(jié)點不入循環(huán)。

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

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

那么為什么使用了vector結(jié)構(gòu)來記錄路徑呢? 因為在下面處理單層遞歸邏輯的時候，要做回溯，使用vector方便來做回溯。

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

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

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

if (cur->left == NULL && cur->right == NULL) { // 遇到葉子節(jié)點 
    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é)點（葉子節(jié)點） 
    result.push_back(sPath); // 收集一個路徑 
    return; 
} 

3.確定單層遞歸邏輯

因為是前序遍歷，需要先處理中間節(jié)點，中間節(jié)點就是我們要記錄路徑上的節(jié)點，先放進path中。

path.push_back(cur->val); 

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

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

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

此時還沒完，遞歸完，要做回溯啊，因為path 不能一直加入節(jié)點，它還要刪節(jié)點，然后才能加入新的節(jié)點。

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

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

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

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

那么代碼應該這么寫：

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é)點 
        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& result) ，定義的是string path，每次都是復制賦值，不用使用引用，否則就無法做到回溯的效果。

那么在如上代碼中，貌似沒有看到回溯的邏輯，其實不然，回溯就隱藏在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(); 
} 

大家應該可以感受出來，如果把 path + "->"作為函數(shù)參數(shù)就是可以的，因為并有沒有改變path的數(shù)值，執(zhí)行完遞歸函數(shù)之后，path依然是之前的數(shù)值(相當于回溯了)

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

迭代法

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

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

C++代碼如下：

class Solution { 
public: 
    vector<string> binaryTreePaths(TreeNode* root) { 
        stack<TreeNode*> treeSt;// 保存樹的遍歷節(jié)點 
        stack<string> pathSt;   // 保存遍歷路徑的節(jié)點 
        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é)點 中 
            string path = pathSt.top();pathSt.pop();    // 取出該節(jié)點對應的路徑 
            if (node->left == NULL && node->right == NULL) { // 遇到葉子節(jié)點 
                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; 
    } 
}; 

當然，使用java的同學，可以直接定義一個成員變量為object的棧Stack stack = new Stack<>();，這樣就不用定義兩個棧了，都放到一個棧里就可以了。

總結(jié)

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

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

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

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

對于本地充分了解遞歸與回溯的過程之后，有精力的同學可以在去實現(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é)點 
        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 
}