剑指offer24：二叉树中和为输入整数值的所有路径。(注意: 在返回值的list中，数组长度大的数组靠前)

1 题目描述

　　输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)。

2 思路和方法

（1）路径的定义：从树的根结点开始往下一直到叶结点

（2）树的遍历

（3）路径的保存：每次找到路径之后，应将路径保存到 ArrayList<ArrayList<Integer>> result 中，最终打印全部路径

思路（1，2，3），方法（递归）：

　　（1）判断树是否为null、是否只有根节点

　　（2）用前序遍历方法，可以首先访问根节点，然后将根节点入队列（或栈均可），并将数值和之前入队列的总和num相加，。栈可直接用pop()将该最后加入栈的节点弹出。本题使用队列，队列：vector<vector<int>>类型使用push_back()压入数据，pop_back()将最后入队的节点弹出；数组ArrayList<ArrayList<Integer>>使用 add()添加数据，使用remove(list.size()-1)将最后入队的节点弹出。

　　（3）判断当前之和否等于给定的值，判断当前节点是否叶节点。若当前值等于给定值，且当前节点是叶节点，则打印路径信息；若当前值小于给定值，且当前节点不是叶节点，则递归调用该节点的左右子树； 若当前值大于给定值，无需递归了（在默认节点值为正数的情况下）。

3 C++核心代码

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     vector<vector<int>> result;
13     vector<int> temp;
14     vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
15         if(root==NULL)
16             return result;
17         temp.push_back(root->val);
18         if(expectNumber-root->val==0 && root->left==NULL && root->right==NULL)
19             result.push_back(temp);
20         FindPath(root->left,expectNumber-root->val);
21         FindPath(root->right,expectNumber-root->val);
22         if(temp.size()>0)
23             temp.pop_back();
24         return result;
25     }
26 };

View Code

4 参考资料

https://blog.csdn.net/LawrenceLan0416/article/details/89707117