后继者:
设计一个算法,找出二叉搜索树中指定节点的“下一个”节点(也即中序后继)。
如果指定节点没有对应的“下一个”节点,则返回null。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/successor-lcci
public class InorderSuccessor {
public static TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
TreeNode prev = null, curr = root;
while (!stack.isEmpty() || curr != null) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
if (prev == p) {
return curr;
}
prev = curr;
curr = curr.right;
}
return null;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(2);
TreeNode tn1 = new TreeNode(1);
TreeNode tn2 = new TreeNode(3);
root.setLeft(tn1);
root.setRight(tn2);
TreeNode tn = inorderSuccessor(root,tn1);
System.out.println(tn);
}
}