मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें ट्री की अंतिम पंक्ति (सबसे गहरे लेवल) का सबसे बायाँ मान ढूंढना है।
उदाहरण: ट्री [3,5,1,6,2,0,8,null,null,7,4] के लिए अंतिम पंक्ति [7,4] है, इसलिए बॉटम लेफ्ट मान 7 है।
DFS + गहराई ट्रैकिंग
- दो वेरिएबल्स
ansऔरmaxLevel(प्रारंभ में -1) रखें। - रिकर्सिव
solve(node, level):- यदि
nodenull है, तो लौटें। - यदि
level > maxLevel, तोans = node->val,maxLevel = level। - पहले
solve(node->left, level+1)कॉल करें (बाएँ पहले ताकि बायाँ मान पहले मिले)। - फिर
solve(node->right, level+1)कॉल करें।
- यदि
- मुख्य फंक्शन से
solve(root, 0)कॉल करें औरansलौटाएँ।
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) { val = data; left = NULL; right = NULL; }
};
class Solution {
public:
int ans = 0;
int maxLevel = -1;
void solve(TreeNode* node, int level = 0) {
if (!node) return;
if (level > maxLevel) {
ans = node->val;
maxLevel = level;
}
solve(node->left, level + 1);
solve(node->right, level + 1);
}
int findBottomLeftValue(TreeNode* root) {
maxLevel = -1;
solve(root);
return ans;
}
};
int main() {
// ट्री बनाने का कोड
Solution ob;
// cout << ob.findBottomLeftValue(root);
return 0;
}
इनपुट
[3,5,1,6,2,0,8,null,null,7,4]
आउटपुट
7