题目描述
输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
原理
首先，采用一种“减法”思想，当检查一棵树从根到叶子节点形成的路径的和是否为target时，先将当前根节点的值 root.val 加入path, 然后检查它的左子树（若非空），看从左子树的根到叶子节点形成的路径的和是否为 expectNumber - root.val (递归), 然后同样的道理去递归检查右子树（若非空），这便是大致的思路。
因为题意没有说节点值全为正数，所以必须递归到根节点才能确定这条路径能否加出expectNumber，而不能到中间节点就加到>=target了，就认为这条路径不行了，假如这条路径后序有0或者负数的情况，还是能加出expectNumber的。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| struct TreeNode
{
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL)
{}
};
class Tree
{
public:
vector<vector<int>> res;
vector<int> temp;
void dfs(TreeNode* root,int number)
{
temp.push_back(root->val);
if (root->val == number && root->left == nullptr && root->right == nullptr)
res.push_back(temp);
if(root->left!=nullptr)
dfs(root->left, number-root->val);
if(root->right!=nullptr)
dfs(root->right, number-root->val);
temp.pop_back();
return;
}
vector<vector<int> > FindPath(TreeNode* root,int expectNumber)
{
if(root == nullptr)
return res;
dfs(root,expectNumber);
return res;
}
};
|
