路经总和

原题：

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。

叶子节点 是指没有子节点的节点。

示例 1： 112. 路经总和 - 图1

  1. 输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
  2. 输出：true

示例 2： 112. 路经总和 - 图2

  1. 输入：root = [1,2,3], targetSum = 5
  2. 输出：false

示例 3：

  1. 输入：root = [1,2], targetSum = 0
  2. 输出：false

提示：

  • 树中节点的数目在范围 [0, 5000] 内
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

解题方法：

解法一：

  1. class Solution {
  2. public:
  3.     vector<int> targetvec;
  4.     bool hasPathSum(TreeNode* root, int targetSum) {
  5.         if(!root) return false;
  6.         if(!root->left&&!root->right&&root->val==targetSum) return true;
  7.         //如果root本身为叶结点的判断
  8.         TreeNode* lastnode=root;//注意！lastnode不应该是全局变量
  9.         Sum(root->left,lastnode);
  10.         Sum(root->right,lastnode);
  11.         for(int i=0;i<targetvec.size();i++)
  12.         {
  13.             if(targetvec[i]==targetSum) return true;
  14.         }
  15.         return false;
  16.     }
  18.     void Sum(TreeNode* node,TreeNode* lastnode)
  19.     {
  20.         if(!node) return;
  21.         node->val+=lastnode->val;  
  22.         if(!node->left&&!node->right)  //两个if条件有区别！
  23.         {
  24.             targetvec.push_back(node->val);
  25.         }
  26.         lastnode=node;   //lastnode指向下一节点
  27.         Sum(node->left,lastnode);
  28.         Sum(node->right,lastnode);
  29.     }
  30. };

解法二（BFS）：

class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == nullptr) {
            return false;
        }
        queue<TreeNode *> que_node;
        queue<int> que_val;
        que_node.push(root);
        que_val.push(root->val);
        while (!que_node.empty()) {
            TreeNode *now = que_node.front();
            int temp = que_val.front();
            que_node.pop();
            que_val.pop();
            if (now->left == nullptr && now->right == nullptr) {
                if (temp == sum) {
                    return true;
                }
                continue;
            }
            if (now->left != nullptr) {
                que_node.push(now->left);
                que_val.push(now->left->val + temp);
            }
            if (now->right != nullptr) {
                que_node.push(now->right);
                que_val.push(now->right->val + temp);
            }
        }
        return false;
    }
};

解法三（官方递归）：

class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == nullptr) {
            return false;
        }
        if (root->left == nullptr && root->right == nullptr) {
            return sum == root->val;
        }
        return hasPathSum(root->left, sum - root->val) ||
               hasPathSum(root->right, sum - root->val);
    }
};

做题小结：

针对解法一：

  1. root本身为nullptr和root本身为叶结点的情况一定要考虑清楚！
  2. 千万要注意不能随便声明全局变量，特别是在有递归的情况下，比如本题如果lastnode被声明为全局变量，那么lastnode的值就会随着遍历的顺序走（如到了左节点，lastnode等于该左节点，到右结点时，右结点对应的lastnode就成了左节点，发生错误）。所以lastnode应该是局部变量，跟随递归。
  3. 注意Sum函数中，两个if条件有区别的，必须是满足第二个if的才能是叶结点
  4. 可以考虑在Sum函数中第二个if处直接判断，而不是放进向量中，来减少空间复杂度
  5. 自己做出来真开心！

针对解法二：

  1. 这是官方的解法，之前我也有考虑过用一个队列存储值，但是就是不知道怎么同步，将值与结点对应起来，现在发现仅仅只需要用两个队列就够了
  2. 或者也可以直接采用C++容器中的pair

针对解法三：

  1. 太巧妙了，直接用sum-root->val来转换为对每个节点本身的值进行判断，不需要像我的递归那样麻烦（我的递归是算出每个节点的和来进行对应）

  2. 要注意区分什么时候递归该有返回值，什么时候不该有

    1. 如果要搜索整棵树，那么递归函数就不需要返回值
    2. 如果只需要找到符合条件的一部分，那么递归函数就需要一个返回值， 因为遇到符合条件的路径了就要及时返回。
  3. 这道题还有一个很重要的地方就是回溯，回溯用于撤消处理结果，像解法一中的lastnode实际上就是为了回溯而存在，如果它为全局变量则无法回溯。而解法三中的回溯则在sum上。