数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++程序：查找二叉搜索树中的中序后继
假设我们有一个二叉搜索树 BST 和另一个节点的值，我们需要在 BST 中找到该节点的中序后继。众所周知，节点 p 的后继是键值大于 p 的值且最小的节点。
因此，如果输入如下所示：
并且 p = 1，则输出将为 2，
为了解决这个问题，我们将遵循以下步骤：
- 定义递归方法 inorderSuccessor()，它将接收根节点和 p
- 如果根节点为空，则
- 返回 null
- 如果根节点的值小于等于 p 的值，则
- 返回 inorderSuccessor(根节点的右子树, p)
- 否则
- option := inorderSuccessor(根节点的左子树, p)
- 返回 (如果 option 为零，则返回根节点，否则返回 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;
}输入
TreeNode *root = new TreeNode(2); root->left = new TreeNode(1); root->right = new TreeNode(3); 1
输出
2
更新于: 2020-11-19
589 次浏览
广告