面试题 34：二叉树中和为某一值的路径.md

试题链接：47. 二叉树中和为某一值的路径 - AcWing题库

方法一：深度优先遍历

• 思路：遍历二叉树时记录路径中遍历的节点，由于树中节点的值不为 0，因此当遍历时路径和大于 sum 时可以提前返回。
• 时间复杂度：O(n)
• 空间复杂度：O(n)

class Solution {
public:
    vector<vector<int>> findPath(TreeNode* root, int sum) {
        if (!root) return {};
        
        vector<vector<int>> ans;
        vector<int> path;
        
        function<void(TreeNode*, int)> dfs = [&](TreeNode* node, int total) {
            if (total > sum) return;
            
            if (!node->left && !node->right) {
                if (total == sum) {
                    ans.push_back(path);
                }
                return;
            }
            
            if (node->left) {
                path.push_back(node->left->val);
                dfs(node->left, total + node->left->val);
                path.pop_back();
            }
            
            if (node->right) {
                path.push_back(node->right->val);
                dfs(node->right, total + node->right->val);
                path.pop_back();
            }
        };
        
        path.push_back(root->val);
        dfs(root, root->val);
        
        return ans;
    }
};