剑指offer-二叉树中和为某一值的路径C++实现

原题链接

#include 
#include 

using namespace std;

struct TreeNode {
    TreeNode *left;
    TreeNode *right;
    int val;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector> FindPath(TreeNode *root, int expectNumber) {
        if (!root)return {};
        // 先序遍历
        dfs(root, expectNumber);
        return ans;
    }

    // 一维数组用于存放每个目标路径节点
    vector tmp;

    // 先序遍历搜索符合要求的节点
    void dfs(TreeNode *root, int x) {
        // 越过叶子节点时，回溯
        if (!root) return;
        // 储存每个遍历过的节点值
        tmp.emplace_back(root->val);
        // 寻找符合要求的路径
        x -= root->val;
        // 走到目标路径的叶节点时，将路径节点的一维数组存到结果数组中
        if (!root->left && !root->right && x == 0) {
            ans.emplace_back(tmp);
        }
        // 先左再右
        dfs(root->left, x);
        dfs(root->right, x);
        // 回溯前删除该节点，避免存储重复和错误的节点值
        tmp.pop_back();
    }

private:
    vector> ans;
};

思路:
先序遍历查找目标路径的节点存到一维数组中，若符合目标路径则使用二维数组存储，回溯时从一维数组中删掉当前节点即可。
时间复杂度O(N)，空间复杂度O(N)