資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告