C++ 中二叉搜索树 (BST) 的中序后继
c++server side programmingprogramming更新于 2025/6/25 2:07:17
假设我们有一棵二叉搜索树，其中有一个节点，我们需要在 BST 中搜索该节点的中序后继。我们知道，节点 p 的后继节点是键值最小且大于 p.val 的节点。
因此，如果输入为 root = [2,1,3]，p = 1，
则输出为 2，
为了解决这个问题，我们将遵循以下步骤 −
定义递归方法 inorderSuccessor()，它将取 root 和 p
如果 root 为 null，则 −
返回null
如果 root 的 val <= p 的 val，则 −
返回 inorderSuccessor(root 的 right，p)
否则
option := inorderSuccessor(root 的 left，p)
返回(如果 option 为零，则返回 root，否则返回 option)
示例
让我们看下面的实现，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
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;
}
}
};
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;
}
输入
{2,1,3},1
输出
2
