Why my mirror's traversal doesn't work?


  • 0
    K

    Hi All,
    I know it's BST, and we could find the successor in O(logN) time.. However, I still want to try out the mirror's traversal. And the following is my code. It failed at one test case:
    Input:
    [2,1,3]
    1
    [2,1,3]
    Output:
    null
    Expected:
    3

    It different from other question and I couldn't use OJ. Can anyone help me on this?

        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            // The first step is to find p, then p.right is okay.
            
            TreeNode curr = root;
            TreeNode pred = null;
            TreeNode res = null;
            
            while(curr != null) {
                if(curr.left == null) {
                    curr = curr.right;
                } else {
                    pred = curr.left;
                    while(pred.right != null && pred.right != curr && pred != p) {
                        pred = pred.right;
                    }
                    
                    if(pred == p) {
                        // System.out.println("Pred's value is -->  " + pred.val);
                        if(pred.right == null) {
                            res = curr;
                            // System.out.println("Successor's value is -->  " + res.val);
                            break;
                        } else {
                            res = pred.right;
                            // System.out.println("Successor's value is -->  " + res.val);
                            break;
                        }
                    } else {
                        if(pred.right == null) {
                            pred.right = curr;
                            curr = curr.left;
                        } else {
                            pred.right = null;
                            curr = curr.right;
                        }
                    }
                }
            }
            return res;
        }
    

Log in to reply
 

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