【二叉树算法题记录】二叉树的所有路径，路径总和——回溯

257. 二叉树的所有路径

题目描述

给你一个二叉树的根节点root ，按任意顺序，返回所有从根节点到叶子节点的路径。

题目分析

其实从根节点往下走，遍历的思路就如下图所示。我们先走到叶子节点（这是一条路径），然后再往上回溯，如果回溯到的上层节点有右孩子，那么就再按照右边的路径往下走（另一条路径）。

1. 递归传入参数及返回值

void traversal(TreeNode* cur, vector<int>& path, vector<string>& result)

cur是当前节点，path用来记录当前路径，result是最终返回的结果。

3. 递归终止条件
   当我们遍历到叶子节点时，就要把当前路径path加入result了。

if(cur->left == NULL && cur->right == NULL) {// 如果当前节点是叶子节点，也就是左右孩子都为空// 也就是说已经遍历了一条根节点到叶子节点的路径// 我们要把这条路径放进result中string sPath;for(int i = 0; i < path.size() - 1; i++){sPath += to_string(path[i]);sPath += "->";}sPath += to_string(path[path.size() - 1]);result.push_back(sPath);return;}

3. 单层递归逻辑
   我们进行的是一个前序遍历，但是需要注意的是当前节点的处理要在递归终止条件之前进行：

path.push_back(cur->val);   // 先将当前节点放进当前path中，再判断结束条件

这是因为所有节点包括叶子节点都要加入path，如果先判断终止，再处理当前节点则会漏掉叶子节点。

在进行左右孩子的遍历时，我们要注意判断节点是否为空：

if(cur->left) {traversal(cur->left, path, result);path.pop_back();    // 回溯}if(cur->right) {traversal(cur->right, path, result);path.pop_back();    // 回溯}

cpp代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void traversal(TreeNode* cur, vector<int>& path, vector<string>& result){path.push_back(cur->val);   // 先将当前节点放进当前path中，再判断结束条件if(cur->left == NULL && cur->right == NULL) {// 如果当前节点是叶子节点，也就是左右孩子都为空// 也就是说已经遍历了一条根节点到叶子节点的路径// 我们要把这条路径放进result中string sPath;for(int i = 0; i < path.size() - 1; i++){sPath += to_string(path[i]);sPath += "->";}sPath += to_string(path[path.size() - 1]);result.push_back(sPath);return;}if(cur->left) {traversal(cur->left, path, result);path.pop_back();    // 回溯}if(cur->right) {traversal(cur->right, path, result);path.pop_back();    // 回溯}}vector<string> binaryTreePaths(TreeNode* root) {vector<int> path;vector<string> result;if(root == NULL) return result;traversal(root, path, result);return result;}
};

112. 路径总和

题目描述

给你二叉树的根节点root和一个表示目标和的整数targetSum。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和targetSum。如果存在，返回true；否则，返回false。

题目分析

其实这题跟上题是一样的，只不过这里多了一个targetSum的判断。

cpp代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void traversal(TreeNode* cur, vector<int>& path, vector<int>& sum){path.push_back(cur->val);if(cur->left == NULL && cur->right == NULL) {cout << "当前路径: ";for(int p : path) {cout << p << ' ';}cout << endl;sum.push_back(accumulate(path.begin(), path.end(), 0));cout << "当前路径总和: " << accumulate(path.begin(), path.end(), 0) << endl;return;}if(cur->left) {traversal(cur->left, path, sum);path.pop_back();}if(cur->right) {traversal(cur->right, path, sum);path.pop_back();}}bool hasPathSum(TreeNode* root, int targetSum) {vector<int> path;vector<int> sum;if(root == NULL) return false;traversal(root, path, sum);if(find(sum.begin(), sum.end(), targetSum) == sum.end()){return false;}else return true;}
};