leetcode/q_112_path_sum.cpp at master · sentry5588/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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void print_stack(string note, stack<TreeNode *> s, bool enable) {
        if (enable == true) {
            cout << note;
            while (s.size() > 0) {
                cout << s.top()->val << ", ";
                s.pop();
            }
            cout << endl;
        }
    }

    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) {
            // cout << "root == nullptr false" << endl;
            return false;
        }
        bool debug_print_enable = false;
        stack<TreeNode *> s;
        s.push(root);
        int path_sum = root->val;
        // int stopper = 0;
        while (s.size() > 0) {
            // stopper++;
            // if (stopper > 20) {
            //     break;
            // }
            // cout << "stopper=" << stopper << ", ";
            // cout << "s.size()=" << s.size() << ": ";
            // print_stack("while begin: ", s, debug_print_enable);
            if (s.top()->left != nullptr) {
                s.push(s.top()->left);
                path_sum = path_sum + s.top()->val;
                // cout << "Go left, path_sum=" << path_sum << endl;
            } else if (s.top()->right != nullptr) {
                s.push(s.top()->right);
                path_sum = path_sum + s.top()->val;
                // cout << "Go right, path_sum=" << path_sum << endl;
            } else {
                if (path_sum == targetSum) {
                    // cout << "True" << endl;
                    return true;
                } else {
                    auto i = s.top();
                    path_sum = path_sum - s.top()->val;
                    cout << "Pop=" << i->val << ", path_sum=" << path_sum << endl;
                    s.pop();
                    if (s.size() == 0) {
                        // cout << "first pop false" << endl;
                        return false;
                    }

                    // print_stack("else-else: ", s, debug_print_enable);
                    // Continue popping from right child
                    while (   (s.top()->right == i)
                           || (s.top()->left == i && s.top()->right == nullptr) ) {
                        i = s.top();
                        path_sum = path_sum - s.top()->val;
                        cout << "Pop=" << i->val << ", path_sum=" << path_sum << endl;
                        s.pop();
                        if (s.size() == 0) {
                            // cout << "while pop false" << endl;
                            return false;
                        }
                    }
                    if (s.top()->right != nullptr) {
                        s.push(s.top()->right);
                        path_sum = path_sum + s.top()->val;
                    }
                }
            }
            // print_stack("while end: ", s, debug_print_enable);
        }
        // cout << "end of program false" << endl;
        return false;
    }
};