数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中 BST II 中的中序后继
假设我们在二叉搜索树中有一个节点，我们必须找到 BST 中该节点的中序后继。如果没有中序后继，则返回 null。我们知道，某个节点的后继是键值大于该节点的值且最小的节点。
我们可以直接访问该节点，但不能访问该树的根。这里每个节点都将引用其父节点。以下是节点的定义 −
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
}如果输入为 −
且节点为 2，则输出为 3。
为解决此问题，我们将遵循以下步骤 −
如果节点的右节点不为 null，则 −
node := node 的右节点
当 node 的左节点不为 null 时，执行该操作 −
node := node 的左节点
返回 node
当 (node 的父节点不为 null 且 node 不等于 node 的父节点的左节点) 时，执行该操作 −
node := node 的父节点
返回 node 的父节点
示例
让我们查看以下实现，以更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int val;
Node* left;
Node* right;
Node* parent;
Node(int v, Node* par = NULL){
val = v;
left = NULL;
right = NULL;
parent = par;
}
};
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->left) {
node = node->parent;
}
return node->parent;
}
};
main(){
Solution ob;
Node *root = new Node(5);
root->left = new Node(3, root);
root->right = new Node(6, root);
root->left->left = new Node(2, root->left);
root->left->right = new Node(4, root->left);
root->left->left->left = new Node(1, root->left->left);
cout << (ob.inorderSuccessor(root->left->left))->val;
}输入
Node *root = new Node(5); root->left = new Node(3, root); root->right = new Node(6, root); root->left->left = new Node(2, root->left); root->left->right = new Node(4, root->left); root->left->left->left = new Node(1, root->left->left); (ob.inorderSuccessor(root->left->left))->val
输出
3
更新于：19-Nov-2020
329 视图
广告