深搜 递归
#include <iostream> using namespace std; struct TreeNode { int val; TreeNode *left, *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: bool hasPathSum(TreeNode *root, int sum) { if(!root) return false; if(root->val == sum && !root->left && !root->right) return true; else return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val); } }; int main(void) { TreeNode *root = new TreeNode(5); TreeNode *node1 = new TreeNode(4); root->left = node1; TreeNode *node2 = new TreeNode(8); root->right = node2; TreeNode *node3 = new TreeNode(11); node1->left = node3; TreeNode *node4 = new TreeNode(13); node2->left = node4; TreeNode *node5 = new TreeNode(4); node2->right = node5; TreeNode *node6 = new TreeNode(7); node3->left = node6; TreeNode *node7 = new TreeNode(2); node3->right = node7; TreeNode *node8 = new TreeNode(1); node5->right = node8; Solution s; cout << s.hasPathSum(root, 22) << endl; return 0; }