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

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

Example 1:

Input: root = [2,1,3], p = 1  2 / \1   3Output: 2

Example 2:

Input: root = [5,3,6,2,4,null,null,1], p = 6      5     / \    3   6   / \  2   4 /   1Output: null

 

M1: recursive

time: O(n), space: O(height)

/** * 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) {        if(root == null) {            return null;        }        if(p.val >= root.val) {            return inorderSuccessor(root.right, p);        } else {            TreeNode left = inorderSuccessor(root.left, p);            if(left != null) {                return left;            } else {                return root;            }        }    }}

 

M2: iterative

分两种情况考虑：p有无右子节点

如果p有右子节点，返回右子树的最左子节点；如果没有，从root开始按inorder遍历找successor

time: O(n), space: O(1)

/** * 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) {        if(root == null) {            return null;        }                if(p.right != null) {            TreeNode cur = p.right;            while(cur.left != null) {                cur = cur.left;            }            return cur;        }                else {            TreeNode s = root, t = null;            while(s.val != p.val) {                if(p.val <= s.val) {                    t = s;                    s = s.left;                } else {                    s = s.right;                }            }            return t;        }    }}