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

传送门

nowcoder
leetcode

题目描述

输入一颗二叉树的根节点和一个整数，（按字典序）打印出二叉树中结点值的和为输入整数的所有路径。
路径定义为从树的根结点开始往下一直到叶结点所经过的结点。

C++ 代码 - nowcoder

/*
	递归实现，按照字典序返回结果
	排序实现：lambda 表达式
*/
class Solution {
public:
    vector<vector<int>> FindPath(TreeNode* root, int target) {
        if (root == nullptr) return vector<vector<int>> {};

        vector<vector<int>> res;
        vector<int> path;
        FindPathCore(res, path, root, target);
        sort(res.begin(), res.end(), [](const vector<int>& a, const vector<int>& b) {
            return a.size() > b.size();
        }); 

        return res;
    }

    void FindPathCore(vector<vector<int>>& res, 
                      vector<int>& path, 
                      TreeNode* node, int sum) {
        if (node == nullptr) return;

        path.push_back(node->val);
        if (node->left == nullptr && node->right == nullptr && node->val == sum) {
            res.push_back(path);
        }

        FindPathCore(res, path, node->left, sum - node->val);
        FindPathCore(res, path, node->right, sum - node->val);
        path.pop_back(); // 当前节点不满足要求则pop，返回其父节点
    }
};

/*
	递归实现，按照字典序返回结果
	排序实现：重载 ()
*/
class Solution {
public:
    struct Compare {
        bool operator()(vector<int>& a, vector<int>& b) {
            return a.size() > b.size();
        }
    };

    vector<vector<int>> FindPath(TreeNode* root, int target) {
        if (root == nullptr) return {};

        vector<vector<int>> res;
        vector<int> path;
        FindPathCore(res, path, root, target);
        sort(res.begin(), res.end(), Compare());

        return res;
    }

    void FindPathCore(vector<vector<int>>& res,
                      vector<int> path, 
                      TreeNode* node, int sum) {
        if (node == nullptr) return;

        path.push_back(node->val);
        if (node->left == nullptr && node->right == nullptr && node->val == sum) {
            res.push_back(path);
        }

        FindPathCore(res, path, node->left, sum - node->val);
        FindPathCore(res, path, node->right, sum - node->val);
        path.pop_back(); // 说明当前节点不满足要求则 pop，返回其父节点
    }
};

C++ 代码 - leetcode

/*
    递归实现，未按照字典序返回结果
*/
class Solution {
public:
    vector<vector<int>> pathTarget(TreeNode* root, int target) {
        dfs(root, target);
        return res;
    }

    void dfs(TreeNode* root, int target) {
        if (root == nullptr) return;

        path.emplace_back(root->val);
        target -= root->val;
        if (root->left == nullptr && root->right == nullptr && target == 0) {
            res.emplace_back(path);
        }

        dfs(root->left, target);
        dfs(root->right, target);
        path.pop_back();
    }

private:
    vector<vector<int>> res;
    vector<int> path;
};

/*
    递归实现，按照字典序返回结果
*/
class Solution {
public:
    vector<vector<int>> pathTarget(TreeNode* root, int target) {
        if (!root) return {};
        
        dfs(root, target);
        sort(res.begin(), res.end(), [&](vector<int> v1, vector<int> v2) {
            return v1.size() > v2.size();
        });
        return res;
    }

    void dfs(TreeNode* node, int target) {
        if (node == nullptr) return;

        path.push_back(node->val);
        if (node->left == nullptr && node->right == nullptr && node->val == target) {
            res.push_back(path);
        }

        dfs(node->left, target - node->val);
        dfs(node->right, target - node->val);
        path.pop_back();
    }

private:
    vector<vector<int>> res;
    vector<int> path;
};