2020-07-02
1.题目描述
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始 往下一直到叶节点所经过的节点形成一条路径。2.题解
深度优先搜索：进行回溯的时候要恢复vector的状态3.代码
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> pathSum(TreeNode* root, int sum) { if (!root) return vector<vector<int>>(0); vector<int> tmp; tmp.push_back(root->val); dfs(root,tmp,root->val,sum); return res; } void dfs(TreeNode* node,vector<int> vec,int sumnow,int sum){ if (!node->left&&!node->right){ if (sumnow==sum){ res.push_back(vec); } return ; } if (node->left){ int tmp=node->left->val; vec.push_back(tmp); dfs(node->left,vec,sumnow+tmp,sum); vec.pop_back(); } if (node->right){ int tmp=node->right->val; vec.push_back(tmp); dfs(node->right,vec,sumnow+tmp,sum); vec.pop_back(); } } vector<vector<int>> res; };