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

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 二叉搜索树中的中序后继 II，我们先来看题面：

https://leetcode-cn.com/problems/inorder-successor-in-bst-ii/

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. You will have direct access to the node but not to the root of the tree. Each node will have a reference to its parent node.

给定一棵二叉搜索树和其中的一个节点 node ，找到该节点在树中的中序后继。

如果节点没有中序后继，请返回 null 。

一个结点 node 的中序后继是键值比 node.val大所有的结点中键值最小的那个。

你可以直接访问结点，但无法直接访问树。每个节点都会有其父节点的引用。节点定义如下：

class Node {undefined

public int val;

public Node left;

public Node right;

public Node parent;

}

进阶：

你能否在不访问任何结点的值的情况下解决问题?

示例

解题

https://blog.csdn.net/weixin_44171872/article/details/108569437

主要思路：

（1）递归；

（2）若当前结点的右子树存在，则在右子树中去找最左边的结点；

（3）否则，向上遍历，既父节点存在，且父节点的右子树是当前子树，知道不满足这两个条件；

（4）返回当前子树的父节点即可；

class Solution {
public:
    Node* inorderSuccessor(Node* node) {
      //右子树存在，则找右子树的最左结点
        if(node->right){
            node=node->right;
            while(node->left){
                node=node->left;
            }
            return node;
        }
        //否则，向上找，找到可能遍历过的根节点，该根节点作为其父节点的
        while(node->parent&&node==node->parent->right){
            node=node->parent;
        }
        return node->parent;
    }
};

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

上期推文：

LeetCode1-500题汇总，希望对你有点帮助！

LeetCode刷题实战501：二叉搜索树中的众数

LeetCode刷题实战502：IPO

LeetCode刷题实战503：下一个更大元素 II

LeetCode刷题实战504：七进制数

LeetCode刷题实战505：迷宫II

LeetCode刷题实战506：相对名次

LeetCode刷题实战507：完美数

LeetCode刷题实战508：出现次数最多的子树元素和