Inorder Successor in BST - Tìm kế tiếp in-order trong cây BST

Cho cây BST và một nút p. Tìm nút kế tiếp in-order (nút có khóa nhỏ nhất lớn hơn p.val).

Ví dụ: cây [2,1,3], p = 1 → kết quả 2.

Giải thuật (Đệ quy BST)

Nếu root.val <= p.val, kế tiếp nằm ở cây con phải. Ngược lại, kế tiếp có thể là root hoặc nằm ở cây con trái → đệ quy trái, nếu không có thì trả root.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) { val = data; left = right = NULL; }
};

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

int main() {
    TreeNode* root = new TreeNode(2);
    root->left = new TreeNode(1);
    root->right = new TreeNode(3);
    TreeNode* p = root->left;
    Solution ob;
    cout << ob.inorderSuccessor(root, p)->val;
    return 0;
}

Đầu vào

{2,1,3}, 1

Đầu ra

2