leetcode 113. Path Sum II

113. Path Sum II:题目链接

dfs +huisu

/**
 * 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:
    void dfs(TreeNode* root, int sum, vector<int>& curPath, vector<vector<int>>& allPath) {
        if (root == NULL) {
            return;
        }
        
        if (root->left == NULL && root->right == NULL) {
            if (root->val == sum) {
                  curPath.push_back(root->val);
                  allPath.push_back(curPath);
                  return;
            }
        }
        
        curPath.push_back(root->val);
        if (root->left != NULL) {
            dfs(root->left, sum - root->val,curPath,allPath);
            curPath.pop_back(); // 回溯
        }
        
        if (root->right != NULL) {
            dfs(root->right, sum - root->val,curPath,allPath);
            curPath.pop_back();  // 回溯
        }
    }
    
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> allPath ;
        vector<int> curPath;
        dfs(root, sum, curPath, allPath);
        return allPath;
    }
};

递归解法

class Solution {
    // 返回root为根节点的二叉树中从根结点到叶子结点其和围殴sum的结点
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) { 
            return res; 
        }
        if (root.left == null && root.right == null && root.val == sum) {  // 叶子结点并且符合该路径上的结点之和 === sum
            List<Integer> list = new ArrayList<>();
            list.add(root.val);
            res.add(list); 
        }
        
        List<List<Integer>> leftRes = pathSum(root.left, sum - root.val); // 返回左子树符合条件的路径
        for (List list : leftRes) {
            list.add(0,root.val);  // 将根节点放在该路径的第一个
            res.add(list);
        }
        
        List<List<Integer>> rightRes = pathSum(root.right, sum - root.val); // 返回右子树符合条件的路径
        for (List list : rightRes) {
            list.add(0,root.val);  // 将根节点放在该路径的第一个
            res.add(list);
        }
        return res;
    }
}