Khôi phục cây từ giao dịch đặt hàng trước trong C ++

Giả sử có một cây nhị phân. Chúng tôi sẽ chạy tìm kiếm độ sâu đặt hàng trước đầu tiên trên gốc của cây nhị phân.

Tại mỗi nút trong đường truyền này, đầu ra sẽ là D số dấu gạch ngang (Ở đây D là độ sâu của nút này), sau đó chúng ta hiển thị giá trị của nút này. Như chúng ta biết nếu độ sâu của một nút là D thì độ sâu của nút con trực tiếp của nó là D + 1 và độ sâu của nút gốc là 0.

Một điều khác chúng ta phải ghi nhớ rằng nếu một nút chỉ có một nút con, nút con đó được đảm bảo là nút con bên trái. Vì vậy, nếu đầu ra S của đường truyền này được đưa ra, thì hãy khôi phục cây và trả về gốc của nó.

Vì vậy, nếu đầu vào giống như "1-2--3--4-5--6--7", thì đầu ra sẽ là

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -

• Xác định một ngăn xếp

• i:=0, n:=kích thước của S

• lvl:=0, num:=0

• trong khi tôi

  • để khởi tạo lvl:=0, khi S [i] giống với '-', hãy cập nhật (tăng lvl lên 1), (tăng i lên 1), làm -

    • không làm gì

  • num:=0

  • while (i

    • num:=num * 10 + (S [i] - '0')

    • (tăng tôi lên 1)

  • trong khi kích thước của st> lvl, do -

    • xóa phần tử khỏi st

  • temp =tạo một nút cây mới với giá trị num

  • nếu không st là trống và không bên trái của phần tử trên cùng của st là null, thì -

    • phần tử bên trái của st:=temp

  • ngược lại khi not st trống thì -

    • bên phải phần tử trên cùng của st:=temp

  • chèn tạm thời vào st

• trong khi kích thước st> 1, do -

  • xóa phần tử khỏi st

• return (nếu st trống thì NULL, nếu không thì phần tử trên cùng của st)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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);
}

Đầu vào

"1-2--3--4-5--6--7"

Đầu ra

3 2 4 1 6 5 7