285-二叉搜索树中的中序后继

LeetCode 285. 二叉搜索树中的中序后继

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

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

示例 1：

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

method

TreeNode *pre = nullptr;
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
    if (!root) return nullptr;
    TreeNode *left = inorderSuccessor(root->left, p);
    if (left) return left;
    if (pre && pre == p) {
        return root;
    }
    pre = root;
    TreeNode *right = inorderSuccessor(root->right, p);
    if (right) return right;
    return nullptr;
}

---

LeetCode 510. 二叉搜索树中的中序后继 II

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

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

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

class Node {
public:
    int val;
    Node *left;
    Node *right;
    Node *parent;
}

示例 1：

输入：tree = [2,1,3], node = 1
输出：2
解析：1 的中序后继结点是 2 。注意节点和返回值都是 Node 类型的。

method

• 如果node有右子树，则其后继在它的下面，就直接找右子树的最左边的节点
• 没有右子树，则后继在它的上面，就需要去找它的父节点，同时还要满足父节点是节点tmp的左孩子，这样的tmp才是node的后继

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;
}