Leetcode_113_Path Sum II

[lihe]

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

Return:

[
   [5,4,11,2],
   [5,8,4,5]
]

题意：给定一个二叉树与整数sum，找出所有的从根节点到野子节点的路径，这些路径上的节点的和为sum。

解题思路：

1. 从根节点深度优先遍历二叉树，先序遍历时将该节点值存储至path栈中，使用path_value累加节点值；
2. 当遍历至叶节点是，检查path_value的值是否为sum，若为sum，将pathpush进入result中；
3. 在后续遍历时，将该节点从path栈中弹出，path_valut减去节点值。

class Solution{
public:
    std::vector<std::vector<int>> pathSum(TreeNode* root, int sum){
        std::vector<std::vector<int>> result;
        std::vector<int> path;
        int path_value = 0;
        preorder(root, path_value, sum, path, result);
        return result;
    }

private:
    void preorder(TreeNode* node, int &path_value,
            int sum, std::vector<int> &path, std::vector<std::vector<int>> &result){
        if(!node){
            return;
        }
        path_value += node -> val;
        path.push_back(node -> val);
        if(!node -> left && !node -> right && path_value == sum){
            result.push_back(path);
        }
        preorder(node -> left, path_value, sum, path, result);
        preorder(node -> right, path_value, sum, path, result);
        path_value -= node -> val;
        path.pop_back();
    }
};