题目：Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum. For example: Given the below binary tree and sum = 22, 题目详情见https://leetcode.com/problems/path-sum-ii/?tab=Description
解析1：先使用迭代法找到满足的叶节点，然后在用回溯法找到从根到该叶节点的路径，但该方法效率低，因为涉及到重路径的复计算了。代码如下：
// 时间复杂度 O(n)，空间复杂度 O(log n) // 先用迭代找到满足条件的叶节点，再从该叶节点回溯到根； // 该代码效率比较低因为涉及到重复计算 class Solution { public: vector<vector<int>> pathSum(TreeNode* root, int sum) { if (!root) return vector<vector<int>>(); stack<pair<TreeNode*, int>> s; s.push(make_pair(root, sum - root -> val)); vector<vector<int>> result; while (!s.empty()) { auto p = s.top().first; sum = s.top().second; s.pop(); if (!root -> left && !root -> right && sum == 0) { vector<int> tmp; // 回溯寻找从root 到 p 的路径, 存入 tmp 中 path(root, p, tmp); result.push_back(tmp); } if (root -> left) s.push(make_pair(root -> left, sum - root -> left -> val)); if (root -> right) s.push(make_pair(root -> right, sum - root -> right -> val)); } return result; } private: bool path(TreeNode* root, TreeNode* p, vector<int>& tmp) { if (!root) return false; if (root == p) { tmp.insert(tmp.begin(), root -> val); return true; } if (path(root -> left, p, tmp) || path(root -> right, p, tmp)) { tmp.insert(tmp.begin(), rooot -> val); return true; } return false; } };解析2: 使用递归法，不仅自上而下找到满足要求的叶节点并且同时也保存从根节点到该叶节点的路径，该解法的效率相比如上一解法大大提高了，代码如下：
// 递归，时间复杂度 O(n)，空间复杂度 O(logn) // 该方法不仅自上而下找到满足要求的叶节点 // 并且在寻找叶节点的过程中，也保存该路径 class Solution { public: vector<vector<int>> pathSum(TreeNode* root, int sum) { vector<vector<int>> result; vector<int> tmp; pathSum(root, sum, tmp, result); return result; } private: // pathSum 函数不仅要把该节点 root 保存在临时路径 tmp 中; // 并且当该函数最终离开该节点时，也需要从临时路径中删除该节点. void pathSum(TreeNode* root, int sum, vector<int>& tmp, vector<vector<int>>& result) { if (!root) return; tmp.push_back(root -> val); if (!root -> left && !root -> right) if (root -> val == sum) result.push_back(tmp); pathSum(root -> left, sum - root -> val, tmp, result); pathSum(root -> right, sum - root -> val, tmp, result); tmp.pop_back(); // 最终离开该节点时，删除该节点 } };