C++ Why Morris Traversal failed???


  • 0

    This Morris Traversal code failed with this case
    [10,5,15,null,null,6,20]
    with output:
    5
    5end
    10
    6
    in
    pow!!!

    for Runtime Error

    You see!!!
    This program went to error when it return false after cout << "pow!!!".
    I really do not understand. Is there anyone can help me out?

    class Solution {
    public:
        bool isValidBST(TreeNode* root) {
            TreeNode* prev = NULL, *cur = root, *tmp;
            while (cur) {
                if (!cur->left) {
                    //
                    cout << cur->val << endl;
                    if (prev) {
                        cout << "in" << endl;
                        if (cur->val < prev->val) {
                            cout << "pow!!!" << endl;
                            return false;
                        }
                    }
                    cout << cur->val << "end" << endl;
                    prev = cur;
                    cur = cur->right;
                } else {
                    tmp = cur->left;
                    while (tmp->right && tmp->right != cur)
                        tmp = tmp->right;
                    if (tmp->right == NULL) {
                        tmp->right = cur;
                        cur = cur->left;
                    } else {
                        tmp->right = NULL;
                        //
                        cout << cur->val << endl;
                        if (prev != NULL && prev->val > cur->val)
                            return false;
                        prev = cur;
                        cur = cur->right;
                    }
                }
            }
            return true;
        }
    };
    

  • 1
    R

    @yong.cao.7731 because the tree is modified when "return false". No runtime error if you mark ret = false, then return ret; at the end of function.


  • 0

    @Raymonm said in C++ Why Morris Traversal failed???:

    Wow,That is great! Thanks for your help!


Log in to reply
 

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