285. Inorder-Successor-in-BST

difficulty: Medium

section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

The successor of a node p is the node with the smallest key greater than p.val.

Example 1:

Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.

Example 2:

Input: root = [5,3,6,2,4,null,null,1], p = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.

Note:

1. If the given node has no in-order successor in the tree, return null.

2. It's guaranteed that the values of the tree are unique.

Method One

这个解法确实更好，因为利用了这个题目本身的BST的性质。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
​
        TreeNode candidate = null;
        TreeNode cur = root;
​
        while (cur != null) {
            if (cur.val > p.val) {
                candidate = cur;
                cur = cur.left;
            } else {
                // cur.val <= p.val
                cur = cur.right;
            }
        }
​
        return candidate;
    }
}
​

Method 2

直接利用 inorder 找到 successor 也很容易

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(p.right != null){
            p = p.right;
            while( p.left != null ) {
                p = p.left;
            }
            return p;
        }
        TreeNode prev = null;
        TreeNode cur = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        while( !stack.isEmpty() || cur != null ) {
            while( cur != null ) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if( prev == p ) {
                return cur;
            }
            prev = cur;
            cur = cur.right;
        }
        return null;
    }
}