题解 | #二叉树中和为某一值的路径(一)#

DFS。。。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
      if (root == nullptr) {
        return false;
      }
      
        //  一个结点和对应的路径累加和
      std::stack<std::pair<TreeNode *, int>> stack_;
      
      stack_.push({root, root->val});
      
      while (!stack_.empty()) {
        auto tmp = stack_.top();
        stack_.pop();
        
        if (tmp.first->left == nullptr && 
            tmp.first->right == nullptr &&
            tmp.second == sum) {
          return true;
        }
        
        if (tmp.first->left) {
          stack_.push({tmp.first->left, tmp.second + tmp.first->left->val});
        }
        if (tmp.first->right) {
          stack_.push({tmp.first->right, tmp.second + tmp.first->right->val});
        }
      }
      
      return false;
    }
};

递归求解：

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