目录

前言

一、方法一

二、方法二

前言

题目链接：LCR 053. 二叉搜索树中的中序后继 – 力扣（LeetCode）

题目：

给定一棵二叉搜索树和它的一个节点 p，请找出按中序遍历的顺序该节点 p 的下一个节点。假设二叉搜索树中节点的值都是唯一的。例如，在下图的二叉搜索树中，节点 8 的下一个节点是节点 9，节点 11 的下一个节点是 nullptr。

一、方法一

解决这个问题的最直观的思路就是采用二叉树的中序遍历。可以用一个布尔变量 isFound 来记录是否已经遍历到节点 p。该变量初始化为 false，遍历到节点 p 就将它设为 true。在这个变量变为 true 之后遍历到的第 1 个节点就是要找的节点。基于这种思路可以编写出如下所示的代码：

class Solution {public:TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {stack st;bool isFound = false;TreeNode* cur = root;while (cur || !st.empty()) {while (cur) {st.push(cur);cur = cur->left; }​cur = st.top();st.pop();if (isFound)break;else if (cur == p)isFound = true;cur = cur->right; }return cur; }};

该算法的时间复杂度是 O(n)，空间复杂度是 O(h)，h 为二叉搜索树的深度。

二、方法二

二叉搜索树中节点 p 的中序遍历下一个节点是所有大于节点 p 的值中值最小的节点。例如，在上图的二叉搜索树中，有 3 个节点的值比节点 8 的值大，分别是节点 9、节点 10 和节点 11，并且节点 9 是 3 个节点中值最小的。

下面按照在二叉搜索树中根据节点的值查找节点的思路来分析。从根节点开始，每到达一个节点就比较根节点的值和节点 p 的值。

  1. 当前节点的值小于或等于节点 p 的值，那么节点 p 的下一个节点应该在它的右子树。

  2. 如果当前节点的值大于节点 p 的值，那么当前节点有可能是它的下一个节点。此时当前节点的值比节点 p 的值大，但节点 p 的下一个节点是所有大于它的节点中值最小的一个，因此接下来前往当前节点的左子树，确定是否能找到值更小但仍然大于节点 p 的值的节点。

重复这样比较，直至找到最后一个大于节点 p 的值的节点，就是节点 p 的下一个节点。

class Solution {public:TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {TreeNode* cur = root;TreeNode* result = nullptr;while (cur) {if (cur->val val) {cur = cur->right; }else {result = cur;cur = cur->left; } }return result; }};

该算法的时间复杂度是 O(h)，空间复杂度是 O(1)。