สมมติว่าเรามี BST ต้นไม้การค้นหาแบบไบนารีและค่าอื่นของโหนด เราต้องหาตัวตายตัวแทนตามลำดับของโหนดนั้นใน BST ดังที่เราทุกคนทราบดีว่าผู้สืบทอดของโหนด p คือโหนดที่มีคีย์ที่เล็กที่สุดที่มากกว่าค่าของ p
ดังนั้นหากอินพุตเป็นแบบ
และ p =1 ผลลัพธ์จะเป็น 2
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดวิธีการเรียกซ้ำ inorderSuccessor() ซึ่งจะทำการรูทและ p
- ถ้ารูทเป็นโมฆะ ดังนั้น:
- คืนค่า null
- ถ้า val ของ root <=val ของ p แล้ว:
- ส่งคืน inorderSuccessor(ทางขวาของ root , p)
- มิฉะนั้น
- option :=inorderSuccessor(left of root , p)
- ผลตอบแทน (หากตัวเลือกเป็นศูนย์ ให้ทำการรูท มิฉะนั้น ตัวเลือก)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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
