题目描述：

设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。

如果指定节点没有对应的“下一个”节点，则返回null。

示例 1:

输入: root = [2,1,3], p = 1

2
/
1 3

输出: 2

示例 2:

输入: root = [5,3,6,2,4,null,null,1], p = 6

  5
 / \
3   6

/
2 4
/
1

输出: null

解题思路一：中序遍历，用双指针，记录当前节点的下一个节点，若当前节点为p，则下一次循环的curr则为我们需要的节点，即后继者

中序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        stack<TreeNode*> st;
        TreeNode *prev=nullptr,*curr=root;
        while(!st.empty()||curr!=nullptr){//注意是或
            while(curr!=nullptr){//左孩子入栈
                st.emplace(curr);
                curr=curr->left;
            }
            curr=st.top();
            st.pop();
            if(prev==p){
                return curr;
            }
            prev=curr;
            curr=curr->right;//取栈顶右孩子
        }
        return nullptr;
    }
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

解题思路二：利用二叉搜索树的性质：左孩子<父节点<右孩子。若p节点有右孩子，则p的后继节点必在p的右子树中。否则p的后继节点在p的祖先中。

后一种情况，从root开始遍历，若node值大于p的值，则将node赋值给successor。

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

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)。

参考链接：https://leetcode.cn/problems/successor-lcci/solution/hou-ji-zhe-by-leetcode-solution-6hgc/