바이너리 트리가 있다고 가정합니다. 바이너리 트리의 루트에서 사전 주문 깊이 우선 검색을 실행할 것입니다.
이 탐색의 각 노드에서 출력은 D 수의 대시(여기서 D는 이 노드의 깊이)가 된 후 이 노드의 값을 표시합니다. 노드의 깊이가 D이면 직계 자식의 깊이는 D+1이고 루트 노드의 깊이는 0입니다.
노드에 자식이 하나만 있는 경우 해당 자식은 왼쪽 자식으로 보장된다는 점을 명심해야 합니다. 따라서 이 탐색의 출력 S가 제공되면 트리를 복구하고 루트를 반환합니다.
따라서 입력이 "1-2--3--4-5--6--7"과 같으면 출력은
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
하나의 스택 정의
-
i :=0, n :=S
의 크기 -
레벨 :=0, 숫자 :=0
-
나는
-
초기화 lvl :=0의 경우, S[i]가 '-'와 같을 때 업데이트(lvl을 1만큼 증가), (i를 1만큼 증가) 다음을 수행합니다. -
-
아무것도 하지 않는다
-
-
숫자 :=0
-
동안 (i
-
숫자 :=숫자 * 10 + (S[i] - '0')
-
(i를 1씩 증가)
-
-
st> lvl의 크기 동안 수행 -
-
st
에서 요소 삭제
-
-
temp =num 값으로 새 트리 노드 생성
-
st가 비어 있지 않고 st의 맨 위 요소 왼쪽에 없으면 null이면 -
-
st의 상단 요소 왼쪽 :=temp
-
-
그렇지 않으면 not st가 비어 있으면 -
-
st의 상단 요소 오른쪽 :=temp
-
-
st에 temp 삽입
-
-
크기가 st> 1인 동안 −
-
st
에서 요소 삭제
-
-
반환(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