Morris solves them all.

Time complexity O(n); Space complexity O(1).

```
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if (!root) return false;
bool o = false;
TreeNode *p, *t = root;
int m = 0;
while (t) {
if (p = t->left) {
int n = p->val;
while (p->right && p->right != t) p = p->right, n += p->val;
if (p->right) {
p->right = NULL;
t = t->right;
m -= n;
} else {
m += t->val;
p->right = t;
if (!p->left && m+n == sum) o = true;
t = t->left;
}
} else {
m += t->val;
t = t->right;
if (!t && m == sum) o = true;
}
}
return o;
}
};
```