Iterative solution in C++


  • 0
    class Solution {
    public:
        bool hasPathSum(TreeNode *root, int sum) {
            std::stack<TreeNode*> stack;
            TreeNode *top, *father, *child;
            int val = 0;
            if (!root)
              return false;
            
            stack.push(root);
            while (!stack.empty()) {
                top = stack.top();
                val += top->val;
                
                if (top->left) {
                    stack.push(top->left);
                } else if (top->right) {
                    stack.push(top->right);
                } else {
                    if (val == sum)
                      return true;
                    
                    child = top;
                    stack.pop();
                    val -= child->val;
                    while (!stack.empty()) {
                        father = stack.top();
                        if (child == father->left && !father->right ||
                            child == father->right) {
                                child = father;
                                stack.pop();
                                val -= child->val;
                            } else {
                                stack.push(father->right);
                                break;
                            }
                    }
                }
            }
            
            return false;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.