Morris Traversal method


  • 0
    X
    public boolean isValidBST(TreeNode root) {
            if (root == null) return true;
            TreeNode cur = root;
            TreeNode pre = null;
            
            while (cur != null) {
                if (cur.left != null) {
                    TreeNode next = cur.left;
                    while (next.right != null && next.right != cur) {
                        next = next.right;
                    }
                    if (next.right == null) {
                        next.right = cur;
                        cur = cur.left;
                    }
                    else {
                        if (pre != null && pre.val >= cur.val) return false;
                        next.right = null;
                        pre = cur;
                        cur = cur.right;
                        
                    }
                }
                else {
                    if (pre != null && pre.val >= cur.val) return false;
                    pre = cur;
                    cur = cur.right;
                    
                }
            }
            return true;
        }

Log in to reply
 

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