053. 二叉搜索树中的中序后继

原题链接

题目描述

给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。

节点 p 的后继是值比 p.val 大的节点中键值最小的节点，即按中序遍历的顺序节点 p 的下一个节点。

示例1

输入：root = [2,1,3], p = 1
输出：2
解释：这里 1 的中序后继是 2。请注意 p 和返回值都应是 TreeNode 类型。

示例 2：

输入：root = [5,3,6,2,4,null,null,1], p = 6
输出：null
解释：因为给出的节点没有中序后继，所以答案就返回 null 了。

提示：

• 树中节点的数目在范围 \([1, 10^4]\) 内。
• \(-10^5 \le Node.val \le 10^5\)
• 树中各节点的值均保证唯一。

---

思路

中序遍历

为了找到二叉搜索树中的节点 p 的中序后继，最直观的方法是中序遍历。由于只需要找到节点 p 的中序后继，因此不需要维护完整的中序遍历序列，只需要在中序遍历的过程中维护上一个访问的节点和当前访问的节点。如果上一个访问的节点是节点 p，则当前访问的节点即为节点 p 的中序后继。

如果节点 p 是最后被访问的节点，则不存在节点 p 的中序后继，返回 null。

代码

C++

/**
 * 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*> stk;
        TreeNode * pre = NULL, *cur = root;
        while (!stk.empty() || cur != nullptr) {
            while (cur) {
                stk.push(cur);
                cur = cur->left;
            }
            cur = stk.top();
            stk.pop();
            if (pre == p) return cur;
            pre = cur;
            cur = cur->right;
        }
        return nullptr;
    }
};