剑指Offer之二叉树中的和为某一路径的值

题目

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

思路

本质上是一个二叉树的先根次序遍历，需要借助于递归的操作。如果是叶子节点，而且路径上节点之和为目标数据，直接存放即可，注意push_back是复制操作，所以直接使用。
如果加上当前节点的值，任然小于目标值，那么需要分别向左和向右孩子进行递归操作；否则递归结束，结束前记着弹出当前节点的数据。

AC代码

class Solution {
  public:
    vector<vector<int>> FindPath(TreeNode* root, int expectNumber) {
        preOrder(root, 0, expectNumber);
        return res;
    }
    // sum是之前节点的累加和，num是目标数据
    void preOrder(TreeNode* root, int sum, int num) {
        if(root == nullptr) {
            return;
        }
        path.push_back(root->val);
        if(root->left == nullptr && root->right == nullptr && root->val + sum == num) {  // 找到结果
            res.push_back(path);

        }else{
            if(root->left != nullptr && root->val + sum <= num) {
                preOrder(root->left, sum + root->val, num);    // 向左查找
            }
            if(root->right != nullptr && root->val + sum <= num) {
                preOrder(root->right, sum + root->val, num);  // 向右查找
            }
        }
        path.pop_back();   // 别忘了弹出
    }

    vector<vector<int>>res;  // 存储路径
    vector<int>path;  // 路径
};