面试题34：二叉树中和为某一值的路径（C++）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    vectorint>> res; //存储决策路径
    vectorint> path; //存储决策元素值
public:
    vectorint>> pathSum(TreeNode* root, int sum) {
        if(root == nullptr) return {};
        prior_sort(root, sum);
        return res;
    }
    void prior_sort(TreeNode* root, int sum)
    {
        if(root == nullptr) return;
        path.push_back(root->val); //1.加入决策路径path
        sum -= root->val; //更新sum值
        if(sum == 0 && root->left == nullptr && root->right == nullptr) //2.找到可行解，加入结果集中
        {
            res.push_back(path);
        }
        //3.进入下一次决策
        prior_sort(root->left, sum);
        prior_sort(root->right, sum);
        path.pop_back(); //4.移出决策路径，即向上回溯，将当前节点从路径path中移出
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {

public:
    vectorint>> pathSum(TreeNode* root, int sum) {
        if(root == nullptr) return {};
        stack sk;
        TreeNode* node = root, *prev_node = nullptr; //prev_node表示上一已被访问节点
        vectorint>> res; //存储决策路径
        vectorint> path; //存储决策元素值
        int tmp_sum = 0;
        while(!sk.empty() || node != nullptr)
        {
            if(node != nullptr)
            {
                tmp_sum += node->val;
                path.push_back(node->val);
                sk.push(node);
                node = node->left; //一直往左遍历左子树
            }
            else
            {
                node = sk.top(); //不能往左了，取得根节点
                if(node->right == nullptr || node->right == prev_node)
                {
                    if(node->left == nullptr && node->right == nullptr && tmp_sum == sum)
                    {
                        res.push_back(path);
                    }
                    path.pop_back();
                    tmp_sum -= node->val;
                    sk.pop();
                    prev_node = node; //标记已使用
                    node = nullptr; //回溯
                }
                else
                {
                    node = node->right; //往右遍历右子树
                }
            }
        }
    return res;
    }
};