PROBLEM

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

难度 中等

MY ANSWER

dfs遍历树，将合适的路径seq加入到res。时间复杂度为O(n)，空间复杂度O(n)。 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //int t = 0;
    vector<vector<int>> res;
    void dfs(TreeNode* root, vector<int> seq, int target) {
        if(target == 0 && !root->left && !root->right) {
            seq.push_back(root->val);
            res.push_back(seq);
            return;
        }
        if(!root->left && !root->right && target != 0) {
            return;
        }
        seq.push_back(root->val);
        if(root->left) {
            dfs(root->left, seq, target - root->left->val);
        }
        if(root->right) {
            dfs(root->right, seq, target - root->right->val);
        }
        return;
    }
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        //t = target;
        vector<int> seq;
        if(!root) {
            return res;
        }
        dfs(root, seq, target - root->val);
        return res;
    }
};

BETTER SOLUTION

dfs最后返回前使用pop进行回溯，不需要传入seq数组作为参数，降低空间复杂度。另外使用c++11新的emplace_back，功能与push_back相同，执行效率更高。时间复杂度与空间复杂度同上。

class Solution {
public:
    //int t = 0;
    vector<vector<int>> res;
    vector<int> seq;
    void dfs(TreeNode* root, int target) {
        if (root == nullptr) {
            return;
        }
        seq.emplace_back(root->val);
        target -= root->val;
        if (root->left == nullptr && root->right == nullptr && target == 0) {
            res.emplace_back(seq);
        }
        dfs(root->left, target);
        dfs(root->right, target);
        seq.pop_back();
    }
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        dfs(root, target);
        return res;
    }
};

SUMMARY

重点掌握回溯在此题中的应用，回溯递归最后返回前要撤销之前的操作。另外注意emplace_back的用法。