经典算法实例应用：后继者（二）

接上文，小编来分享第二种解题思路：

方法二：利用二叉搜索树的性质

二叉搜索树的一个性质是中序遍历序列单调递增，因此二叉搜索树中的节点 p 的后继节点满足以下条件：​

后继节点的节点值大于 p 的节点值；
后继节点是节点值大于 p 的节点值的所有节点中节点值最小的一个节点。

利用二叉搜索树的性质，可以在不做中序遍历的情况下找到节点 p 的后继节点。

如果节点 p 的右子树不为空，则节点 p 的后继节点在其右子树中，在其右子树中定位到最左边的节点，即为节点 p 的后继节点。

如果节点 p 的右子树为空，则需要从根节点开始遍历寻找节点 p 的祖先节点。

将答案初始化为 null。用 node 表示遍历到的节点，初始时node=root。每次比较 node 的节点值和 p 的节点值，执行相应操作：

如果 node 的节点值大于 p 的节点值，则 p 的后继节点可能是 node 或者在 node 的左子树中，因此用 node 更新答案，并将 node 移动到其左子节点继续遍历；
如果 node 的节点值小于或等于 p 的节点值，则 p 的后继节点可能在 node 的右子树中，因此将 node 移动到其右子节点继续遍历。

由于在遍历过程中，当且仅当 node 的节点值大于 p 的节点值的情况下，才会用 node 更新答案，因此当节点 p 有后继节点时一定可以找到后继节点，当节点 p 没有后继节点时答案一定为 null。

代码

Python3

class Solution: def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode: successor = None if p.right: successor = p.right while successor.left: successor = successor.left return successor node = root while node: if node.val > p.val: successor = node node = node.left else: node = node.right return successor

Java

class Solution { public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { TreeNode successor = null; if (p.right != null) { successor = p.right; while (successor.left != null) { successor = successor.left; } return successor; } TreeNode node = root; while (node != null) { if (node.val > p.val) { successor = node; node = node.left; } else { node = node.right; } } return successor; } }

C#

public class Solution { public TreeNode InorderSuccessor(TreeNode root, TreeNode p) { TreeNode successor = null; if (p.right != null) { successor = p.right; while (successor.left != null) { successor = successor.left; } return successor; } TreeNode node = root; while (node != null) { if (node.val > p.val) { successor = node; node = node.left; } else { node = node.right; } } return successor; } }

复杂度分析

• 时间复杂度：O(n) ，其中 n 是二叉搜索树的节点数。遍历的节点数不超过二叉搜索树的高度，平均情况是 O(logn)，最坏情况是 O(n) 。
• 空间复杂度：O(1) 。