Cây nhị phân Chế độ xem bên phải trong C ++

Giả sử chúng ta có một cây nhị phân, nếu chúng ta nhìn thấy cây từ phía bên phải, thì chúng ta có thể thấy một số phần tử của nó. chúng ta phải hiển thị các yếu tố đó. Vì vậy, nếu cây như -

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

• Chúng tôi sẽ tạo một phương pháp trợ giúp cho dfs. Điều này sẽ lấy tree_node, một mảng để chứa các câu trả lời và cấp độ. Mức ban đầu là 0. Các dfs sẽ hoạt động như bên dưới -
• nếu nút là null, thì trả về
• if level =độ dài của mảng câu trả lời, sau đó chèn giá trị của nút vào mảng ans
• dfs (bên phải của nút, ans, mức + 1)
• dfs (bên trái của nút, ans, cấp + 1)
• Từ hàm chính, hãy gọi dfs () bằng cách sử dụng gốc của cây và một mảng trống, mức ban đầu là 0, vì vậy đây sẽ là dfs (root, ans)

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;
void print_vector(vector<int> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class TreeNode{
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data){
         val = data;
         left = right = NULL;
      }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      } else {
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
         temp->right = new TreeNode(val);
      else
         temp->right = new TreeNode(0);
         return;
      } else {
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
   public:
   void dfs(TreeNode* node, vector <int>& ans, int level = 0){
      if(!node) return;
      if(level == ans.size())ans.push_back(node->val);
      dfs(node->right, ans, level + 1);
      dfs(node->left, ans, level + 1);
   }
   vector<int> rightSideView(TreeNode* root) {
      vector <int> ans;
      dfs(root, ans);
      return ans;
   }
};
main(){
   vector<int> v = {1,2,3,NULL,5,NULL,4};
   TreeNode *root = make_tree(v);
   Solution ob;
   print_vector(ob.rightSideView(root));
}

Đầu vào

[1,2,3,null,5,null,4]

Đầu ra

[1, 3, 4, ]