数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究二叉搜索树的中序后继节点（C++ 版）
假设我们有一个二叉搜索树和其中的一个节点，我们必须在二叉搜索树中搜索该节点的中序后继节点。正如我们所知，节点 p 的后继节点是键小于 p.val 的最小键的节点。
所以，如果输入为 root = [2,1,3], p = 1,
那么输出将是 2,
为了解决这个问题，我们将按照以下步骤进行操作 -
定义递归方法 inorderSuccessor()，它将采用根和 p
如果 root 为空，那么 -
返回 null
如果 root 的 val <= p 的 val，那么 -
返回 inorderSuccessor(root 的右子树, p)
否则
option := inorderSuccessor(root 的左子树, 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;
}输入
{2,1,3},1输出
2
更新时间： 2020 年 11 月 18 日
125 次浏览
广告