बाइनरी ट्री को बाएं से देखने पर जो नोड्स दिखाई देते हैं, उन्हें लेफ्ट साइड व्यू कहते हैं। उदाहरण ट्री के लिए आउटपुट [1, 2, 5] है।
समाधान दृष्टिकोण (DFS)
हम प्री-ऑर्डर DFS का उपयोग करते हैं जहां हम पहले बाएं सबट्री को एक्सप्लोर करते हैं:
- एक सरणी
retऔर वेरिएबलlvl = -1रखें। dfs(node, level)फंक्शन:- यदि नोड नल है, तो वापस लौटें।
- यदि
level > lvl, तोlvl = levelऔर नोड का मानretमें जोड़ें। - पहले बाएं, फिर दाएं बच्चे पर पुनरावृति करें (
level + 1के साथ)।
- मुख्य फंक्शन से
dfs(root, 0)कॉल करें औरretवापस करें।
C++ कार्यान्वयन
#include <bits/stdc++.h> using namespace std; void print_vector(vectorv) { 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; } }; class Solution { public: vector ret; int lvl; void dfs(TreeNode* node, int c = 1) { if (!node) return; if (c > lvl) { lvl = c; ret.push_back(node->val); } dfs(node->left, c + 1); dfs(node->right, c + 1); } vector solve(TreeNode* root) { lvl = -1; dfs(root, 0); return ret; } }; int main() { TreeNode *root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->right = new TreeNode(5); root->right->right = new TreeNode(4); Solution ob; print_vector(ob.solve(root)); return 0; }
इनपुट
TreeNode *root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->right = new TreeNode(5); root->right->right = new TreeNode(4);
आउटपुट
[1,2,5]