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 3
Output: 2
Example 2:
Input: root = [5,3,6,2,4,null,null,1], p = 6
5
/ \
3 6
/ \
2 4
/
1
Output: null
思路: 首先找到P点,同时记录过程中最后一个左拐的点,也就是有可能是大于p的第一个点 (如果p没有右边儿子的话)
如果p有右边儿子,那么就是右边儿子最左边的那个node,否则就是last left turn node;
/**
* 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 || p == null) {
return null;
}
TreeNode pre = null;
TreeNode node = root;
while(node != p) {
if(node.val > p.val) {
pre = node;
node = node.left;
} else if(node.val < p.val) {
node = node.right;
} else {
break;
}
}
if(node.right != null) {
return findLeft(node.right);
} else {
return pre;
}
}
private TreeNode findLeft(TreeNode node) {
TreeNode res = null;
while(node != null) {
res = node;
node = node.left;
}
return res;
}
}