[[417387]]

相信很多同學都會疑惑，遞歸函數(shù)什么時候要有返回值，什么時候沒有返回值，特別是有的時候遞歸函數(shù)返回類型為bool類型。

那么接下來我通過詳細講解如下兩道題，來回答這個問題：

• 112.路徑總和
• 113.路徑總和ii

112. 路徑總和

題目地址：https://leetcode-cn.com/problems/path-sum/

給定一個二叉樹和一個目標和，判斷該樹中是否存在根節(jié)點到葉子節(jié)點的路徑，這條路徑上所有節(jié)點值相加等于目標和。

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

示例: 給定如下二叉樹，以及目標和 sum = 22，

返回 true, 因為存在目標和為 22 的根節(jié)點到葉子節(jié)點的路徑 5->4->11->2。

思路

這道題我們要遍歷從根節(jié)點到葉子節(jié)點的的路徑看看總和是不是目標和。

遞歸

可以使用深度優(yōu)先遍歷的方式(本題前中后序都可以，無所謂，因為中節(jié)點也沒有處理邏輯)來遍歷二叉樹

• 確定遞歸函數(shù)的參數(shù)和返回類型

參數(shù)：需要二叉樹的根節(jié)點，還需要一個計數(shù)器，這個計數(shù)器用來計算二叉樹的一條邊之和是否正好是目標和，計數(shù)器為int型。

再來看返回值，遞歸函數(shù)什么時候需要返回值?什么時候不需要返回值?這里總結(jié)如下三點：

• 如果需要搜索整顆二叉樹且不用處理遞歸返回值，遞歸函數(shù)就不要返回值。(這種情況就是本文下半部分介紹的113.路徑總和ii)
• 如果需要搜索整顆二叉樹且需要處理遞歸返回值，遞歸函數(shù)就需要返回值。(這種情況我們在236. 二叉樹的最近公共祖先介紹)
• 如果要搜索其中一條符合條件的路徑，那么遞歸一定需要返回值，因為遇到符合條件的路徑了就要及時返回。(本題的情況)

而本題我們要找一條符合條件的路徑，所以遞歸函數(shù)需要返回值，及時返回，那么返回類型是什么呢?

如圖所示：

112.路徑總和

圖中可以看出，遍歷的路線，并不要遍歷整棵樹，所以遞歸函數(shù)需要返回值，可以用bool類型表示。

所以代碼如下：

bool traversal(treenode* cur, int count) // 注意函數(shù)的返回類型 

• 確定終止條件

首先計數(shù)器如何統(tǒng)計這一條路徑的和呢?

不要去累加然后判斷是否等于目標和，那么代碼比較麻煩，可以用遞減，讓計數(shù)器count初始為目標和，然后每次減去遍歷路徑節(jié)點上的數(shù)值。

如果最后count == 0，同時到了葉子節(jié)點的話，說明找到了目標和。

如果遍歷到了葉子節(jié)點，count不為0，就是沒找到。

遞歸終止條件代碼如下：

if (!cur->left && !cur->right && count == 0) return true; // 遇到葉子節(jié)點，并且計數(shù)為0 
if (!cur->left && !cur->right) return false; // 遇到葉子節(jié)點而沒有找到合適的邊，直接返回 

• 確定單層遞歸的邏輯

因為終止條件是判斷葉子節(jié)點，所以遞歸的過程中就不要讓空節(jié)點進入遞歸了。

遞歸函數(shù)是有返回值的，如果遞歸函數(shù)返回true，說明找到了合適的路徑，應該立刻返回。

代碼如下：

if (cur->left) { // 左 （空節(jié)點不遍歷） 
    // 遇到葉子節(jié)點返回true，則直接返回true 
    if (traversal(cur->left, count - cur->left->val)) return true; // 注意這里有回溯的邏輯 
} 
if (cur->right) { // 右 （空節(jié)點不遍歷） 
    // 遇到葉子節(jié)點返回true，則直接返回true 
    if (traversal(cur->right, count - cur->right->val)) return true; // 注意這里有回溯的邏輯 
} 
return false; 

以上代碼中是包含著回溯的，沒有回溯，如何后撤重新找另一條路徑呢。

回溯隱藏在traversal(cur->left, count - cur->left->val)這里， 因為把count - cur->left->val 直接作為參數(shù)傳進去，函數(shù)結(jié)束，count的數(shù)值沒有改變。

為了把回溯的過程體現(xiàn)出來，可以改為如下代碼：

if (cur->left) { // 左 
    count -= cur->left->val; // 遞歸，處理節(jié)點; 
    if (traversal(cur->left, count)) return true; 
    count += cur->left->val; // 回溯，撤銷處理結(jié)果 
} 
if (cur->right) { // 右 
    count -= cur->right->val; 
    if (traversal(cur->right, count)) return true; 
    count += cur->right->val; 
} 
return false; 

整體代碼如下：

class solution { 
private: 
    bool traversal(treenode* cur, int count) { 
        if (!cur->left && !cur->right && count == 0) return true; // 遇到葉子節(jié)點，并且計數(shù)為0 
        if (!cur->left && !cur->right) return false; // 遇到葉子節(jié)點直接返回 
 
        if (cur->left) { // 左 
            count -= cur->left->val; // 遞歸，處理節(jié)點; 
            if (traversal(cur->left, count)) return true; 
            count += cur->left->val; // 回溯，撤銷處理結(jié)果 
        } 
        if (cur->right) { // 右 
            count -= cur->right->val; // 遞歸，處理節(jié)點; 
            if (traversal(cur->right, count)) return true; 
            count += cur->right->val; // 回溯，撤銷處理結(jié)果 
        } 
        return false; 
    } 
 
public: 
    bool haspathsum(treenode* root, int sum) { 
        if (root == null) return false; 
        return traversal(root, sum - root->val); 
    } 
}; 

以上代碼精簡之后如下：

class solution { 
public: 
    bool haspathsum(treenode* root, int sum) { 
        if (root == null) return false; 
        if (!root->left && !root->right && sum == root->val) { 
            return true; 
        } 
        return haspathsum(root->left, sum - root->val) || haspathsum(root->right, sum - root->val); 
    } 
}; 

是不是發(fā)現(xiàn)精簡之后的代碼，已經(jīng)完全看不出分析的過程了，所以我們要把題目分析清楚之后，在追求代碼精簡。 這一點我已經(jīng)強調(diào)很多次了!

迭代

如果使用棧模擬遞歸的話，那么如果做回溯呢?

此時棧里一個元素不僅要記錄該節(jié)點指針，還要記錄從頭結(jié)點到該節(jié)點的路徑數(shù)值總和。

c++就我們用pair結(jié)構來存放這個棧里的元素。

定義為：pair

這個為棧里的一個元素。

如下代碼是使用棧模擬的前序遍歷，如下：(詳細注釋)

class solution { 
 
public: 
    bool haspathsum(treenode* root, int sum) { 
        if (root == null) return false; 
        // 此時棧里要放的是pair<節(jié)點指針，路徑數(shù)值> 
        stack<pair<treenode*, int>> st; 
        st.push(pair<treenode*, int>(root, root->val)); 
        while (!st.empty()) { 
            pair<treenode*, int> node = st.top(); 
            st.pop(); 
            // 如果該節(jié)點是葉子節(jié)點了，同時該節(jié)點的路徑數(shù)值等于sum，那么就返回true 
            if (!node.first->left && !node.first->right && sum == node.second) return true; 
 
            // 右節(jié)點，壓進去一個節(jié)點的時候，將該節(jié)點的路徑數(shù)值也記錄下來 
            if (node.first->right) { 
                st.push(pair<treenode*, int>(node.first->right, node.second + node.first->right->val)); 
            } 
 
            // 左節(jié)點，壓進去一個節(jié)點的時候，將該節(jié)點的路徑數(shù)值也記錄下來 
            if (node.first->left) { 
                st.push(pair<treenode*, int>(node.first->left, node.second + node.first->left->val)); 
            } 
        } 
        return false; 
    } 
}; 

如果大家完全理解了本地的遞歸方法之后，就可以順便把leetcode上113. 路徑總和ii做了。

113. 路徑總和ii

題目地址：https://leetcode-cn.com/problems/path-sum-ii/

給定一個二叉樹和一個目標和，找到所有從根節(jié)點到葉子節(jié)點路徑總和等于給定目標和的路徑。

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

示例: 給定如下二叉樹，以及目標和 sum = 22，

思路

113.路徑總和ii要遍歷整個樹，找到所有路徑，所以遞歸函數(shù)不要返回值!

如圖：

113.路徑總和ii

為了盡可能的把細節(jié)體現(xiàn)出來，我寫出如下代碼(這份代碼并不簡潔，但是邏輯非常清晰)

class solution { 
private: 
    vector<vector<int>> result; 
    vector<int> path; 
    // 遞歸函數(shù)不需要返回值，因為我們要遍歷整個樹 
    void traversal(treenode* cur, int count) { 
        if (!cur->left && !cur->right && count == 0) { // 遇到了葉子節(jié)點且找到了和為sum的路徑 
            result.push_back(path); 
            return; 
        } 
 
        if (!cur->left && !cur->right) return ; // 遇到葉子節(jié)點而沒有找到合適的邊，直接返回 
 
        if (cur->left) { // 左 （空節(jié)點不遍歷） 
            path.push_back(cur->left->val); 
            count -= cur->left->val; 
            traversal(cur->left, count);    // 遞歸 
            count += cur->left->val;        // 回溯 
            path.pop_back();                // 回溯 
        } 
        if (cur->right) { // 右 （空節(jié)點不遍歷） 
            path.push_back(cur->right->val); 
            count -= cur->right->val; 
            traversal(cur->right, count);   // 遞歸 
            count += cur->right->val;       // 回溯 
            path.pop_back();                // 回溯 
        } 
        return ; 
    } 
 
public: 
    vector<vector<int>> pathsum(treenode* root, int sum) { 
        result.clear(); 
        path.clear(); 
        if (root == null) return result; 
        path.push_back(root->val); // 把根節(jié)點放進路徑 
        traversal(root, sum - root->val); 
        return result; 
    } 
}; 

至于113. 路徑總和ii 的迭代法我并沒有寫，用迭代方式記錄所有路徑比較麻煩，也沒有必要，如果大家感興趣的話，可以再深入研究研究。

總結(jié)

本篇通過leetcode上112. 路徑總和 和 113. 路徑總和ii 詳細的講解了 遞歸函數(shù)什么時候需要返回值，什么不需要返回值。

這兩道題目是掌握這一知識點非常好的題目，大家看完本篇文章再去做題，就會感受到搜索整棵樹和搜索某一路徑的差別。

對于112. 路徑總和，我依然給出了遞歸法和迭代法，這種題目其實用迭代法會復雜一些，能掌握遞歸方式就夠了!

本文轉(zhuǎn)載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關注。轉(zhuǎn)載本文請聯(lián)系代碼隨想錄公眾號。