递归函数什么时候有返回值，什么时候没有？

❝取决于是否需要遍历整棵二叉树

❞

112。路径和

给定一棵二叉树和一个目标和，确定是否存在从树的根节点到叶节点的路径。该 Path 中所有节点的值之和等于目标和。

说明：叶子节点是指没有子节点的节点。

示例：给定以下二叉树，目标和 sum = 22，

返回 true，因为从根节点到叶节点的路径为 5->4->11->2。目标金额 22.

Idea

这道题，我们需要遍历从根节点到叶子节点的路径，看看金额是否是目标金额。

递归

可以使用深度遍历来遍历一道题（这题可以前序、中序、后序都可以，没关系，因为中间节点没有处理逻辑） 。二叉树

1. 设置递归函数的参数和返回类型

参数：需要二叉树的根节点，还需要一个计数器。该计数器用于计算二叉树的边和是否恰好是目标和。计数器的类型为int。

“再看返回值，递归函数什么时候需要返回值？什么时候递归函数不需要返回值？”

在二叉树中：我的左下角的值是多少？ ，我的结论是：

“如果需要搜索整棵二叉树，则递归函数不需要返回值。如果要搜索一条满足条件的路径，则递归函数需要返回值因为遇到满足条件的路径，及时返回“

二叉树：我的左下角的值是多少？ ，由于需要遍历树的所有路径才能找到深度最深的叶子节点，因此递归函数不返回值。

这道题，我们需要找到一条满足条件的路径，所以递归函数必须有返回值，并及时返回。返回类型是什么？

如图所示：

如图所示，遍历路线不必遍历整棵树，因此递归函数必须返回一个可以用布尔类型表示的值。

所以代码如下：

bool traversal(TreeNode* cur, int count)   // 注意函数的返回类型

1. 设置字段的终止条件

首先，计数器是如何计算这条路径的总和的？

不要收集然后判断是否等于目标金额，那么代码会更麻烦。可以使用减量，让计数器重置为目标量，然后在每次遍历时减去路径中某个节点的值。

如果最终计数==0并且同时到达叶子节点，则说明已经找到了目标和。

如果遍历到一个叶子节点，计数不为0，则说明没有找到。

递归终止条件代码如下：

if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
if (!cur->left && !cur->right) return false; // 遇到叶子节点而没有找到合适的边，直接返回

1. 定义单级递归逻辑

由于终止条件是确定一个叶子节点，所以递归时不要让空节点进入递归过程。

递归函数有返回值。如果递归函数返回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;

上面的代码包含向后移动。没有退路。如何回去另谋出路？

追踪被隐藏遍历(cur->left, count - cur->left->val)这里因为直接使用count - cur->left->val参数传递，函数结束，计数值不变。

可以改为如下代码来体现退货流程：

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 - cur->right->val)) 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;
    }
};

如果你完全理解了局部递归方法，就可以 113. Path Sum II 是leetcode。

113。路径和II

给定一棵二叉树和一个目标和，找到从根节点到叶子节点的所有路径，其总和等于给定的目标和。

说明：叶子节点是指没有子节点的节点。

示例：给定以下二叉树，目标和 sum = 22，

Idea

113。 Path Sum 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。我还没有为 Path Sum II 编写迭代方法。重新记录所有路径既麻烦又不必要。如果感兴趣的话，可以深入研究一下。

总结

这篇文章通过leetcode 112. Path Sum和113. Path Sum II，详细解释了递归函数什么时候应该返回值，什么时候不应该返回值。

这两个问题是获取这个知识点非常好的问题。如果您在阅读本文后回答问题，您就会知道搜索整棵树和搜索特定路径之间的区别。

112。对于路径求和，我仍然给出了递归方法和迭代方法。当使用迭代方法时，这样的问题其实比较困难，掌握递归方法就足够了！