​LeetCode刷题实战285：二叉搜索树中的顺序后继

今天和大家聊的问题叫做 二叉搜索树中的中序后继，我们先来看题面：https://leetcode-cn.com/problems/inorder-successor-in-bst/

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

The successor of a node p is the node with the smallest key greater than p.val.

给你一个二叉搜索树和其中的某一个结点，请你找出该结点在树中顺序后继的节点。结点 p 的后继是值比 p.val 大的结点中键值最小的结点。

示例

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

解题

这道题让我们求二叉搜索树的某个节点的中序后继节点，那么根据 BST 的性质知道其中序遍历的结果是有序的，博主最先用的方法是用迭代的中序遍历方法，然后用一个 bool 型的变量b，初始化为 false，进行中序遍历，对于遍历到的节点，首先看如果此时b已经为 true，说明之前遍历到了p，那么此时返回当前节点，如果b仍为 false，看遍历到的节点和p是否相同，如果相同，此时将b赋为 true，那么下一个遍历到的节点就能返回了，参见代码如下：

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        stack<TreeNode*> s;
        bool b = false;
        TreeNode *t = root;
        while (t || !s.empty()) {
            while (t) {
                s.push(t);
                t = t->left;
            }
            t = s.top(); s.pop();
            if (b) return t;
            if (t == p) b = true;
            t = t->right;
        }
        return NULL;
    }
};

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。