题目描述 输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 题目解析 (1)要找到符合条件的路径，首先需要遍历整个二叉树，在遍历过程中使用一个一维数组记录当前走过的所有节点的值，并用给定的值不断减去走过的节点值。 (2)当走到叶节点时判断给定的值是否为0，如果为0，保存到二维数组。 (3)当遇到不符合条件的值时进行回溯，回溯时注意：回溯需要删除一维数组中最后一个值，并且需要对给定的值加上删除的一维数组的最后一个值。 代码以及测试用例如下
#pragma once #include<iostream> #include<vector> #include<algorithm> using namespace std; struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; class Solution { public: vector<vector<int>> Vout; vector<int> Vin; void dfs(TreeNode* root, int expectNumber, vector<int>&Vin, vector<vector<int>>&Vout) { expectNumber -= root->val; Vin.push_back(root->val); if (!root->left && !root->right&&expectNumber == 0) { Vout.push_back(Vin); } if (root->left) { dfs(root->left, expectNumber, Vin, Vout); } if (root->right) { dfs(root->right, expectNumber, Vin, Vout); } //回溯 expectNumber += Vin.back(); Vin.pop_back(); } vector<vector<int> > FindPath(TreeNode* root, int expectNumber) { if (!root)return Vout; dfs(root, expectNumber, Vin, Vout); return Vout; } }; int main() { //创建测试用例 TreeNode *root = new TreeNode(10); TreeNode *a1 = new TreeNode(5); TreeNode *a2 = new TreeNode(4); TreeNode *a3 = new TreeNode(7); TreeNode *b1 = new TreeNode(12); root->left = a1; root->right = b1; a1->left = a2; a1->right = a3; a2->left = nullptr; a2->right = nullptr; a3->left = nullptr; a3->right = nullptr; b1->left = nullptr; b1->right = nullptr; Solution s1; vector<vector<int>> Vout = s1.FindPath(root, 22); for (int i = 0; i < Vout.size(); i++) { for (int j = 0; j < Vout[i].size(); j++) { cout <<Vout[i][j]<<" "; } cout << endl; } }结果如下
