[[417387]]

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

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

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

112. 路徑總和

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

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

說明: 葉子節點是指沒有子節點的節點。

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

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

思路

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

遞歸

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

• 確定遞歸函數的參數和返回類型

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

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

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

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

如圖所示：

112.路徑總和

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

所以代碼如下：

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

• 確定終止條件

首先計數器如何統計這一條路徑的和呢?

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

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

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

遞歸終止條件代碼如下：

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

• 確定單層遞歸的邏輯

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

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

代碼如下：

if (cur->left) { // 左 （空節點不遍歷） 
    // 遇到葉子節點返回true，則直接返回true 
    if (traversal(cur->left, count - cur->left->val)) return true; // 注意這里有回溯的邏輯 
} 
if (cur->right) { // 右 （空節點不遍歷） 
    // 遇到葉子節點返回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 直接作為參數傳進去，函數結束，count的數值沒有改變。

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

if (cur->left) { // 左 
    count -= cur->left->val; // 遞歸，處理節點; 
    if (traversal(cur->left, count)) return true; 
    count += cur->left->val; // 回溯，撤銷處理結果 
} 
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; // 遇到葉子節點，并且計數為0 
        if (!cur->left && !cur->right) return false; // 遇到葉子節點直接返回 
 
        if (cur->left) { // 左 
            count -= cur->left->val; // 遞歸，處理節點; 
            if (traversal(cur->left, count)) return true; 
            count += cur->left->val; // 回溯，撤銷處理結果 
        } 
        if (cur->right) { // 右 
            count -= cur->right->val; // 遞歸，處理節點; 
            if (traversal(cur->right, count)) return true; 
            count += cur->right->val; // 回溯，撤銷處理結果 
        } 
        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); 
    } 
}; 

是不是發現精簡之后的代碼，已經完全看不出分析的過程了，所以我們要把題目分析清楚之后，在追求代碼精簡。 這一點我已經強調很多次了!

迭代

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

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

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

定義為：pair

這個為棧里的一個元素。

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

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

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

說明: 葉子節點是指沒有子節點的節點。

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

思路

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

如圖：

113.路徑總和ii

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

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

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

總結

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

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

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

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