/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: // 每个节点都充当单独的树来遍历一次 int FindPath(TreeNode* root, int sum) { if (root == nullptr) return ans; dfs(root, sum); FindPath(root->left, sum); FindPath(root->right, sum); return ans; } // dfs 查询以某个节点为根的路径条数有多少 void dfs(TreeNode* root, int sum) { if (root == nullptr) return; if (sum == root->val) ans++; dfs(root->left, sum - root->val); dfs(root->right, sum - root->val); } private: int ans = 0; };