สมมติว่ามี binary tree เราต้องหา vertical order traversal ของค่าของโหนด ถ้ามีสองโหนดอยู่ในแถวและคอลัมน์เดียวกัน ลำดับควรเป็นจากซ้ายไปขวา
เช่น ถ้าอินพุทเป็นแบบ
ผลลัพธ์จะเป็น [[9],[3,15],[20],[7]]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −
กำหนดแมป m
กำหนดฟังก์ชัน solve() รับ node, x เริ่มต้นที่ 0
ถ้า node เป็น null แล้ว −
คืนค่า
solve(left ของ node, x - 1)
solve(right ของ node, x + 1)
แทรกค่าของ node ที่ท้ายของ m[x]
จากเมธอดหลัก ทำดังนี้ −
ถ้า root เป็น null แล้ว −
คืนค่า {}
กำหนดคิว q
แทรก { 0, root } ลงใน q
แทรกค่าของ node ที่ท้ายของ m[0]
ลูป while (q ไม่ว่าง) ทำ −
sz := ขนาดของ q
ลูป while sz ไม่เป็นศูนย์ ลด sz ทุกการวน ทำ −
curr := สมาชิกแรกของ q
ลบสมาชิกออกจาก q
node = สมาชิกที่สองของ curr
x := สมาชิกแรกของ curr
ถ้า left ของ node ไม่ใช่ null แล้ว −
แทรก { x - 1, left ของ node } ลงใน q
left ของ node ที่ท้ายของ m[x - 1]
ถ้า right ของ node ไม่ใช่ null แล้ว −
แทรก { x - 1, right ของ node } ลงใน q
right ของ node ที่ท้ายของ m[x - 1]
กำหนดอาร์เรย์ 2 มิติ ret
ลูปสำหรับแต่ละ key-value pair 'it' ของ m ทำ −
แทรกค่าของ it ลงใน ret
คืนค่า 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: map<int, vector<int> > m; void solve(TreeNode* node, int x = 0){ if (!node || node->val == 0) return; solve(node->left, x - 1); solve(node->right, x + 1); m[x].push_back(node->val); } static bool cmp(vector<int>& a, vector<int>& b){ return a[0] != b[0] ? a[0] < b[0] : a[1] < b[1]; } vector<vector<int> > verticalOrder(TreeNode* root){ if (!root) return {}; queue<pair > q; q.push({ 0, root }); m[0].push_back(root->val); while (!q.empty()) { int sz = q.size(); while (sz--) { pair<int, TreeNode*> curr = q.front(); q.pop(); TreeNode* node = curr.second; int x = curr.first; if (node->left && node->left->val != 0) { q.push({ x - 1, node->left }); m[x - 1].push_back(node->left->val); } if (node->right && node->right->val != 0) { q.push({ x + 1, node->right }); m[x + 1].push_back(node->right->val); } } } vector<vector<int> > ret; map<int, vector<int> >::iterator it = m.begin(); while (it != m.end()) { ret.push_back(it->second); it++; } return ret; } }; main(){ Solution ob; vector<int> v = {3,9,20,NULL,NULL,15,7}; TreeNode *root = make_tree(v); print_vector(ob.verticalOrder(root)); } อินพุท
{3,9,20,NULL,NULL,15,7} เอาต์พุท
[[9, ],[3, 15, ],[20, ],[7, ],]
