C++ Non-recursive, based on Morris Traversal


  • 0
    A

    Drawback: Can't bail out early even if we found fault in the middle, or the tree will be devastated.
    But I do like this beautiful in-place non-recursive traversal method. Kudos to Morris who devised this method, not me.

    class Solution {
    public:
        bool isValidBST(TreeNode* root) {
            int v;
            bool f = false, o = true;
            TreeNode *p, *h = root;
            while (h) {
                if (p = h->left) {
                    while (p->right && p->right != h) p = p->right;
                    if (p->right) {
                        p->right = NULL;
                        if (h->val <= v) o = false;
                        v = h->val;
                        h = h->right;
                    } else {
                        p->right = h;
                        h = h->left;
                    }
                } else {
                    if (f && h->val <= v) o = false;
                    f = true;
                    v = h->val;
                    h = h->right;
                }
            }
            return o;
        }
    };
    

Log in to reply
 

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