LeetCode/pathSum.cpp at master · ysdeal/LeetCode · GitHub

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
61
62
/**
 * Definition for binary tree
 * struct TreeNode {
 *       int val;
 *       TreeNode *left;
 *       TreeNode *right;
 *       TreeNode(int x): val(x), left(NULL), right(NULL) {}
 *   };
 *
 * Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum
 */
vector<vector<int>> pathSum(TreeNode *root, int sum){
    vector<vector<int>> out;
    if (root==NULL) return out;

    stack<TreeNode*> st;
    TreeNode *top, *child, *father;
    vector<int> vt;
    int stsum = 0;

    st.push(root);
    vt.push_back(root->val);
    stsum = root->val;

    while(!st.empty()){
        top = st.top();
        if(top->left)
        {
            st.push(top->left);
            stsum += top->left->val;
            vt.push_back(top->left->val);
        }else if(top->right){
            st.push(top->right);
            stsum += top->right->val;
            vt.push_back(top->right->val);
        }else{
            if (stsum == sum)
                out.push_back(vt);
            child = top;
            st.pop();
            vt.pop_back();
            stsum -= child->val;

            while(!st.empty()){
                father = st.top();
                if(father->left == child && father->right == NULL || father->right == child)
                {
                    child = father;
                    st.pop();
                    vt.pop_back();
                    stsum -= child->val;
                }else{
                    st.push(father->right);
                    vt.push_back(father->right->val);
                    stsum += father->right->val;
                    break;
                }
            }
        }
    }
    return out;
}