C++で二分木の葉を見つける

二分木があるとします。すべての葉を集めて取り除き、木が空になるまで繰り返します。

したがって、入力が次のような場合

その場合、出力は[[4,5,3]、[2]、[1]]

これを解決するには、次の手順に従います-

• 1つのマップszを定義する

• 1つの2D配列retを定義する

• 関数dfs（）を定義します。これはノードを取ります

• ノードがnullの場合、-

  • sz [ノードの値]：=1 + dfs（ノードの左側）とdfs（ノードの右側）の最大値

• retのサイズ

  • アレイの温度を定義する

  • retの最後にtempを挿入します

• ret [sz [val of node]-1]

  の最後にノードのvalを挿入します

• sz[ノードの値]を返す

• メインの方法から、次のようにします-

• dfs（root）

• retを返す

例

理解を深めるために、次の実装を見てみましょう-

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

入力

{1,2,3,4,5}

出力

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