สมมติว่ามี binary tree เราจะเก็บและลบใบไม้ทั้งหมดและทำซ้ำจนกว่าต้นไม้จะว่างเปล่า
เช่น ถ้าอินพุทเป็นแบบ
ผลลัพธ์จะเป็น [[4,5,3],[2],[1]]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −
กำหนดแมป sz
กำหนดอาร์เรย์ 2 มิติ ret
กำหนดฟังก์ชัน dfs() รับ node
ถ้า node เป็น null แล้ว −
sz[val ของ node] := 1 + สูงสุดของ dfs(left ของ node) และ dfs(right ของ node)
ถ้าขนาดของ ret < sz[val ของ node] แล้ว −
กำหนดอาร์เรย์ temp
แทรก temp ที่ท้ายของ ret
แทรก val ของ node ที่ท้ายของ ret[sz[val ของ node] - 1]
คืนค่า sz[val ของ node]
จากเมธอดหลัก ทำดังนี้ −
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, ],]
