Tìm lá cây nhị phân trong C ++

Giả sử chúng ta có một cây nhị phân. Chúng tôi sẽ thu gom và loại bỏ tất cả các lá và lặp lại cho đến khi hết cây.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là [[4,5,3], [2], [1]]

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

• Xác định một bản đồ sz

• Xác định một mảng 2D ret

• Xác định một hàm dfs (), hàm này sẽ sử dụng nút,

• nếu nút là null, thì -

  • sz [val của nút]:=1 + tối đa dfs (bên trái của nút) và dfs (bên phải của nút)

• nếu kích thước của ret

  • Xác định tạm thời mảng

  • chèn tạm thời vào cuối ret

• chèn val của nút vào cuối ret [sz [val của nút] - 1]

• trả về sz [val of node]

• Từ phương thức chính, thực hiện như sau -

• dfs (gốc)

• trả lại ret

Ví dụ

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto< > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class TreeNode{
public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      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:
   unordered_map <int, int> sz;
   vector < vector <int< > ret;
   int dfs(TreeNode* node){
      if(!node) return 0;
         sz[node->val] = 1 + max(dfs(node->left), dfs(node->right));
      if(ret.size() < sz[node->val]){
         vector <int< temp;
         ret.push_back(temp);
      }
      ret[sz[node->val] - 1].push_back(node->val);
      return sz[node->val];
   }
   vector<vector<int<> findLeaves(TreeNode* root) {
      dfs(root);
      return ret;
   }
};
main(){
   Solution ob;
   vector<int< v = {1,2,3,4,5};
   TreeNode *root = make_tree(v);
   print_vector(ob.findLeaves(root));
}

Đầu vào

{1,2,3,4,5}

Đầu ra

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