接上文小编来分享第二种解题思路方法二利用二叉搜索树的性质二叉搜索树的一个性质是中序遍历序列单调递增因此二叉搜索树中的节点 p 的后继节点满足以下条件后继节点的节点值大于 p 的节点值后继节点是节点值大于 p 的节点值的所有节点中节点值最小的一个节点。利用二叉搜索树的性质可以在不做中序遍历的情况下找到节点 p 的后继节点。如果节点 p 的右子树不为空则节点 p 的后继节点在其右子树中在其右子树中定位到最左边的节点即为节点 p 的后继节点。如果节点 p 的右子树为空则需要从根节点开始遍历寻找节点 p 的祖先节点。将答案初始化为 null。用 node 表示遍历到的节点初始时noderoot。每次比较 node 的节点值和 p 的节点值执行相应操作如果 node 的节点值大于 p 的节点值则 p 的后继节点可能是 node 或者在 node 的左子树中因此用 node 更新答案并将 node 移动到其左子节点继续遍历如果 node 的节点值小于或等于 p 的节点值则 p 的后继节点可能在 node 的右子树中因此将 node 移动到其右子节点继续遍历。由于在遍历过程中当且仅当 node 的节点值大于 p 的节点值的情况下才会用 node 更新答案因此当节点 p 有后继节点时一定可以找到后继节点当节点 p 没有后继节点时答案一定为 null。代码Python3class 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 successorJavaclass 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) 。
