力扣-二叉树-112路径总和

思路

使用先序遍历，回溯不同节点的值

代码 class Solution { public: bool havePath = false; void prefix(TreeNode* node, int target, int result){ if(node->left == nullptr && node->right == nullptr && result + node->val == target){ havePath = true; return ; } if(havePath) return; if(node->left){ result += node->val; prefix(node->left, target, result); result -= node->val; } if(node->right){ result += node->val; prefix(node->right, target, result); result -= node->val; } } bool hasPathSum(TreeNode* root, int targetSum) { if(root == nullptr) return false; prefix(root, targetSum, 0); return havePath; } };