原题链接在这里:https://leetcode.com/problems/inorder-successor-in-bst/
题目:
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
.
题解:
successor could be自己的parent, or 右子树中最左的点.
For both cases, if p.val < root.val, update successor as root. Otherwise, root needs to be bigger, root = root.right.
Time Complexity: O(h).
Space: O(1).
AC Java:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if(root == null || p == null){
return null;
}
TreeNode successor = null;
while(root != null){
if(p.val < root.val){
successor = root;
root = root.left;
}else{
root = root.right;
}
}
return successor;
}
}