# Untitled

unknown
plain_text
21 days ago
2.2 kB
2
Indexable
Never
```#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// Define the structure of a tree node
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// Function to build a binary tree from a given array
TreeNode* buildTree(const vector<int>& nodes) {
if (nodes.empty() || nodes[0] == -1) return NULL;

TreeNode* root = new TreeNode(nodes[0]);
queue<TreeNode*> q;
q.push(root);
int i = 1;

while (i < nodes.size()) {
TreeNode* current = q.front();
q.pop();

// Build left child
if (i < nodes.size() && nodes[i] != -1) {
current->left = new TreeNode(nodes[i]);
q.push(current->left);
}
i++;

// Build right child
if (i < nodes.size() && nodes[i] != -1) {
current->right = new TreeNode(nodes[i]);
q.push(current->right);
}
i++;
}

return root;
}

// Function to find the median of the nodes at the deepest level
double findDeepestLevelMedian(TreeNode* root) {
if (!root) return 0.0;

queue<TreeNode*> q;
q.push(root);
vector<int> deepestLevelNodes;

while (!q.empty()) {
int size = q.size();
deepestLevelNodes.clear();  // Clear the previous level's nodes

for (int i = 0; i < size; ++i) {
TreeNode* node = q.front();
q.pop();
deepestLevelNodes.push_back(node->val);

if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}

sort(deepestLevelNodes.begin(), deepestLevelNodes.end());
int n = deepestLevelNodes.size();

// Find the median
if (n % 2 == 1) {
return deepestLevelNodes[n / 2];  // Odd number of elements
} else {
return (deepestLevelNodes[n / 2 - 1] + deepestLevelNodes[n / 2]) / 2.0;  // Even number of elements
}
}

int main() {
vector<int> nodes = {1, 2, 3, 4, 5, -1, 6, 7, 8};  // Example input
TreeNode* root = buildTree(nodes);
double median = findDeepestLevelMedian(root);
cout << "Median of deepest level nodes: " << median << endl;
return 0;
}
```