สมมติว่ามีไบนารีทรี เราจะทำการค้นหาแบบพรีออเดอร์ในเชิงลึกก่อนบนรูทของไบนารีทรี
ที่แต่ละโหนดในการข้ามผ่านนี้ เอาต์พุตจะเป็นจำนวน D ของขีดกลาง (ในที่นี้ D คือความลึกของโหนดนี้) หลังจากนั้นเราแสดงค่าของโหนดนี้ ดังที่เรารู้ว่าความลึกของโหนดเป็น D หรือไม่ ความลึกของโหนดย่อยที่อยู่ติดกันคือ D+1 และความลึกของโหนดรูทคือ 0
อีกอย่างที่เราต้องจำไว้คือถ้าโหนดมีลูกเพียงคนเดียว เด็กคนนั้นรับประกันว่าจะเป็นลูกด้านซ้าย ดังนั้น หากให้เอาท์พุต S ของการข้ามผ่านนี้ ให้กู้คืนต้นไม้และคืนรากของมัน
ดังนั้น หากอินพุตเป็น "1-2--3--4-5--6--7" ผลลัพธ์จะเป็น
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดหนึ่งสแต็ก st
-
ผม :=0, n :=ขนาดของ S
-
เลเวล :=0, num :=0
-
ในขณะที่ฉัน
-
สำหรับการเริ่มต้น lvl :=0 เมื่อ S[i] เหมือนกับ '-' ให้อัปเดต (เพิ่มเลเวลทีละ 1) (เพิ่ม i ขึ้น 1) ทำ -
-
ไม่ทำอะไรเลย
-
-
num :=0
-
ในขณะที่ (i
-
num :=num * 10 + (S[i] - '0')
-
(เพิ่ม i ขึ้น 1)
-
-
ในขณะที่ขนาดของ st> lvl ทำ −
-
ลบองค์ประกอบออกจาก st
-
-
temp =สร้าง Tree Node ใหม่โดยมีค่า num
-
ถ้าไม่ใช่ st ว่างเปล่า และไม่เหลือองค์ประกอบบนสุดของ st จะเป็นโมฆะ −
-
ด้านซ้ายขององค์ประกอบด้านบนของ st :=temp
-
-
มิฉะนั้นเมื่อ st ไม่ว่างเปล่า ดังนั้น −
-
ด้านขวาขององค์ประกอบด้านบนของ st :=temp
-
-
ใส่อุณหภูมิลงใน st
-
-
ในขณะที่ขนาดของ st> 1 ทำ −
-
ลบองค์ประกอบออกจาก st
-
-
return (ถ้า st ว่างเปล่า แสดงว่าเป็น NULL มิฉะนั้น องค์ประกอบบนสุดของ st)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void inord(TreeNode *root){
if(root != NULL){
inord(root->left);
cout << root->val << " ";
inord(root->right);
}
}
class Solution {
public:
TreeNode* recoverFromPreorder(string S) {
stack<TreeNode*> st;
int i = 0;
int n = S.size();
int lvl = 0;
int num = 0;
while (i < n) {
for (lvl = 0; S[i] == '-'; lvl++, i++)
;
num = 0;
while (i < n && S[i] != '-') {
num = num * 10 + (S[i] - '0');
i++;
}
while (st.size() > lvl)
st.pop();
TreeNode* temp = new TreeNode(num);
if (!st.empty() && !st.top()->left) {
st.top()->left = temp;
}
else if (!st.empty()) {
st.top()->right = temp;
}
st.push(temp);
}
while (st.size() > 1)
st.pop();
return st.empty() ? NULL : st.top();
}
};
main(){
Solution ob;
TreeNode *root = ob.recoverFromPreorder("1-2--3--4-5--6--7");
inord(root);
} อินพุต
"1-2--3--4-5--6--7"
ผลลัพธ์
3 2 4 1 6 5 7
