代码随想录刷题——二叉树篇（十二）

112. 路径总和

递归法：

class Solution{ public: bool sumPath(TreeNode* node,int count){ # 如果该节点是叶子节点且count被减到0了，那么就返回true if(!node->left&&!node->right&&count==0) return true; # 如果该节点是叶子节点且count不为0，那么就返回false if(!node->left&&!node->right) return false; # 对当前节点进行操作，如果左右子节点存在，继续判断 if(node->left){ if(sumPath(node->left,count-node->left->val)) return true; } if(node->right){ if(sumPath(node->right,count-node->right->val)) return true; } # 左右子节点都判断完了没有返回true，那就是false return false; } bool hasPathSum(TreeNode* root, int targetSum) { if(!root) return false; return sumPath(root,targetSum-root->val); } };

迭代法：

class Solution{ public: bool hasPathSum(TreeNode* root,int targetSum){ if(!root) return false; # 用pair存储 该节点 和 到该节点的路径值的和 两个信息 queue<pair<TreeNode*,int>> qu; qu.push(root,root->val); while(!qu.empty()){ pair<TreeNode*,int> node=qu.front(); qu.pop(); # 和递归类似，如果是叶子节点且count被减到0 if(!node.first->left&&!node.first->right&&node.second==targetSum) return true; # 当前节点的左右子节点操作 if(node.first->left) qu.push(pair<TreeNode*,int>(node.first->left,node.second+node.first->left->val)); if(node.first->right) qu.push(pair<TreeNode*,int>(node.first->right,node.second+node.first->right->val)); } return false; } };

113. 路径总和 II

递归法：

class Solution{ public: void sumPath(TreeNode* node,int target,vector<vector<int>>& ans,vector<int>& vec){ if(!node->left&&!node->right&&target==0){ ans.push_back(vec); return ; } if(!node->left&&!node->right) return ; if(node->left){ vec.push_back(node->left->val); sumPath(node->left,target-node->left->val,ans,vec); vec.pop_back(); } if(node->right){ vec.push_back(node->right->val); sumPath(node->right,target-node->right->val,ans,vec); vec.pop_back(); } return ; } vector<vector<int>> pathSum(TreeNode* root, int targetSum) { vector<vector<int>> ans; if(!root) return ans; vector<int> vec; vec.push_back(root->val); sumPath(root,targetSum-root->val,ans,vec); return ans; } };

其他：

（1）再看递归三部曲：

a.确定参数和返回类型（如果需要遍历整个二叉树，可以不需要返回值，如果需要操作递归返回值，就需要返回值）

b.确定终止条件（如果在叶子节点终止，就可以通过条件判断避免遍历空节点）

c.确定单层递归逻辑（最外层区域要如何操作和return）

（2）113题中的回溯可以用全局变量实现，我的写法里是用的引用变量，也可以用全局变量来实现
（3）这两道题和之前的所有路径那道题类似，都是递归+回溯的形式