Leetcode daily challenge: 25 Dec,2024.
Problem link
BFS is perfect when we are dealing specifically with rows/levels of a binary tree. With BFS, we handle one row of the tree at a time.
Here, we need to find the maximum value in each row. We can simply perform a BFS and for each row, keep track of the maximum value we have seen so far.
void bfs( TreeNode* node, vector<int>& result){ queue<TreeNode *>Q; Q.push(node); int qSize = Q.size(); int count =0; while(!Q.empty()){ count = 0; priority_queue<int>heap; qSize = Q.size(); while(count<qSize){// for each level/row find max value count++; TreeNode* temp = Q.front(); Q.pop(); heap.push(temp->val); if(temp->left != NULL) Q.push(temp->left); if(temp->right != NULL) Q.push(temp->right); }//while ends if(heap.size()) result.push_back(heap.top()); } } vector<int> largestValues(TreeNode* root) { if(root == NULL) return {}; vector<int>result; bfs(root, result);///call bfs return result; } Video link with detailed explanation will be found here.
Top comments (0)