每日一题 剑指offer（二叉树中和为某一值的路径）

编程是很多偏计算机、人工智能领域必须掌握的一项技能，此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”，通过每天一道编程题目来强化和锻炼自己的编程能力（最起码不会忘记编程）

特别说明：编程题来自“牛客网”和“领扣”以及热心小伙伴的题目。由于小白有时想锻炼某一类编程方法，所以提供的代码不一定是最优解，但是本文提供的编程代码均为通过测试代码。

二叉树中和为某一值的路径

题目描述

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

二叉树结构为

struct TreeNode {
 int val;
 struct TreeNode *left;
 struct TreeNode *right;
 TreeNode(int x) :
     val(x), left(NULL), right(NULL) {
 }
};

解析

1.按先序遍历把当前节点cur的左孩子依次入栈同时保存当前节点，每次更新当前路径的和sum；

2.判断当前节点是否是叶子节点以及sum是否等于expectNumber，如果是，把当前路径放入结果中。

3.遇到叶子节点cur更新为NULL，此时看栈顶元素，如果栈顶元素的把栈顶元素保存在last变量中，同时弹出栈顶元素，当期路径中栈顶元素弹出，sum减掉栈顶元素，这一步骤不更改cur的值；

4.如果步骤3中的栈顶元素的右孩子存在且右孩子之前没有遍历过，当前节点cur更新为栈顶的右孩子，此时改变cur=NULL的情况。

代码

class Solution {
public:
   vector<vector<int> > FindPath(TreeNode* root,int expectNum) {
   vector<vector<int> > res;  
   if (root == NULL)
       return res;
   stack<TreeNode *> s;
   s.push(root);
   int sum = 0; //当前和
   vector<int> curPath; //当前路径
   TreeNode *cur = root; //当前节点
   TreeNode *last = NULL; //保存上一个节点
   while (!s.empty()){
       if (cur == NULL){
           TreeNode *temp = s.top();
           if (temp->right != NULL && temp->right != last){
               cur = temp->right; //转向未遍历过的右子树
           }else{
               last = temp; //保存上一个已遍历的节点
               s.pop();
               curPath.pop_back(); //从当前路径删除
               sum -= temp->val;
           }  }
       else{
           s.push(cur);
           sum += cur->val;
           curPath.push_back(cur->val);
           if (cur->left == NULL && cur->right == NULL && sum == expectNum){
               res.push_back(curPath);
           }
           cur = cur->left; //先序遍历，左子树先于右子树
       }
   }
   return res;
   }
};