给定一个二叉查找树(什么是二叉查找树)，以及一个节点，求该节点在中序遍历的后继，如果没有则返回null
在线评测地址：点击此处前往
样例 1:
输入: {1,#,2}, node with value 1
输出: 2
解释:
1
2样例 2:
输入: {2,1,3}, node with value 1
输出: 2
解释:
2
/ 1 3【题解】
首先要确定中序遍历的后继:
使用循环实现:
使用递归实现:
null, 则直接返回当前根节点; 反之返回左子树递归查找的结果.在递归实现中, 暂存左子树递归查找的结果就相当于循环实现中维护的祖先节点.
另外在《九章算法面试高频题冲刺班》有讲到更优化的解法，具体代码如下
public class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode successor = null;
while (root != null && root.val != p.val) {
if (root.val > p.val) {
successor = root;
root = root.left;
} else {
root = root.right;
}
}
if (root == null) {
return null;
}
if (root.right == null) {
return successor;
}
root = root.right;
while (root.left != null) {
root = root.left;
}
return root;
}
}
// version:高频题班
public class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if (root == null || p == null) {
return null;
}
if (root.val <= p.val) {
return inorderSuccessor(root.right, p);
} else {
TreeNode left = inorderSuccessor(root.left, p);
return (left != null) ? left : root;
}
}更多题解参见 ：九章算法官网
【LeetCode/LintCode】题解丨 美团面试真题：二叉查找树的中序后继
原文：https://www.cnblogs.com/lintcode/p/13534297.html