leetcode 112 路径总和特别关注

 1 /*
 2  * @lc app=leetcode.cn id=112 lang=cpp
 3  *
 4  * [112] 路径总和
 5  */
 6 
 7 // @lc code=start
 8 /**
 9  * Definition for a binary tree node.
10  * struct TreeNode {
11  *     int val;
12  *     TreeNode *left;
13  *     TreeNode *right;
14  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
15  * };
16  */
17 class Solution {
18 public:
19     /*
20     如果需要搜索整颗二叉树，那么递归函数就不要返回值，
21     如果要搜索其中一条符合条件的路径，递归函数就需要返回值，因为遇到符合条件的路径了就要及时返回。
22     
23     所以本次搜索需要返回值
24 
25     1. 确定递归函数的参数和返回值类型
26     2、确定终止条件
27     2. 确定单层递归的逻辑
28     */
29     
30     bool hasPathSum(TreeNode* root, int sum) {
31         if(root==nullptr) return false;
32 
33         if(!root->left&&!root->right&&root->val==sum)
34             return true;
35         return hasPathSum(root->left,sum-root->val) || 
36                 hasPathSum(root->right,sum-root->val);
37     }
38 
39     /*  思路：
40     class Solution {
41 private:
42     bool traversal(TreeNode* cur, int count) {
43         if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
44         if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回
45 
46         if (cur->left) { // 左
47             count -= cur->left->val; // 递归，处理节点;
48             if (traversal(cur->left, count)) return true;
49             count += cur->left->val; // 回溯，撤销处理结果
50         }
51         if (cur->right) { // 右
52             count -= cur->right->val; // 递归，处理节点;
53             if (traversal(cur->right, count)) return true;
54             count += cur->right->val; // 回溯，撤销处理结果
55         }
56         return false;
57     }
58 
59 public:
60     bool hasPathSum(TreeNode* root, int sum) {
61         if (root == NULL) return false;
62         return traversal(root, sum - root->val);
63     }
64 };
65 
66 
67     */
68 };
69 // @lc code=end
leetcode 112 路径总和 特别关注

leetcode 112 路径总和特别关注
