C++ Non-recursive O(1) space solution, based on Morris Traversal


  • 0
    A

    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;
        }
    };
    

Log in to reply
 

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