113. Path Sum II

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution
{
private:
    vector<vector<int>> result;
    void pathSum(TreeNode *i_root, int sum, vector<int> pathValues)
    {
        if(!i_root) return;

        sum -= i_root->val;
        pathValues.push_back(i_root->val);
        if(!i_root->left && !i_root->right && sum == 0) result.push_back(pathValues);

        pathSum(i_root->left, sum, pathValues);
        pathSum(i_root->right, sum, pathValues);
    }
public:
    // vector<vector<int>> pathSum(TreeNode* root, int sum)
    vector<vector<int>> pathSum(TreeNode *i_root, int sum)
    {
        pathSum(i_root, sum, vector<int>{});

        return result;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

// it is obvious the recursion version is slow
// since at every step, we could only handle one node, but we have to handle function stack, which is too heavy for one node's process
// so we should fix out this question by non recursion methord

class Solution
{
public:
    // vector<vector<int>> pathSum(TreeNode* root, int sum)
    vector<vector<int>> pathSum(TreeNode *m_root, int sum)
    {
        vector<int> pathValues;
        vector<vector<int>> result;
        stack<TreeNode *> parentNodes;

        for(auto iter = m_root; iter || !parentNodes.empty(); )
        {
            if(iter) // at this condition, the node is valid, we continually go left
            {
                sum -= iter->val;
                pathValues.push_back(iter->val);

                if(!iter->left && !iter->right && sum == 0) result.push_back(pathValues);

                parentNodes.push(iter);
                iter = iter->left;
            }
            else // at this condition, the node is invalid
            {
                iter = parentNodes.top(); // so we need to get a valid node
                parentNodes.pop();

                // no matter the last node locates at the left subtree or the right subtree
                // we will never go to the left tree, so we cut it
                iter->left = nullptr;

                // if the iter->right is valid, we could to and check the right subtree
                // but at the same time, we must cut the right subtree, otherwise we will enter a dead loop
                // we go right, and come back to the current node, then we find the right subtree is valid, so we go right again
                // also, we have push the current node into the path, since there may have a valid answer at the right subtree
                if(iter->right)
                {
                    parentNodes.push(iter);
                    iter = iter->right;

                    parentNodes.top()->right = nullptr;
                }
                else
                {
                    // if the iter->right is invalid, the current node is useless
                    // we just drop it, and hope go back to its parent to continue the process
                    sum += iter->val;
                    pathValues.pop_back();
                    iter = nullptr;
                }
            }
        }

        return result;
    }
};