【leetcode】285. 二叉搜索树中的顺序后继

给你一个二叉搜索树和其中的某一个结点，请你找出该结点在树中顺序后继的节点。

结点 p 的后继是值比 p.val 大的结点中键值最小的结点。

思路

一开始我是按照寻找找某节点的后继去写的

class Solution {
   
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
   
        if (p->right) {
   
            p = p->right;
            while (p->left) p = p->left;
            return p;
        }
        stack<TreeNode*>s;
        s.push(nullptr);
        TreeNode* cur = root;
        while(cur != p) {
   
            if (p->val < cur->val) {
   
                s.push(cur);
                cur = cur->left;
            } else {
   
                s.push(cur);
                cur = cur->right;
            }
        }
        while (s.top() != nullptr && s.top()->right== p) {
   
            p = s.top();
            s.pop();
        }
        return s.top();
    }
};

很长，也比较慢

后来看别人的代码，是这样写的

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

直接根据二叉搜索树的性质去寻找的最大最小的节点。
感觉是二分查找，分治的思想。
凡是p->val < cur->val , 那么cur 就是一个可行的解。