Cho gốc của cây tối đa (maximum tree): mỗi node có giá trị lớn hơn mọi giá trị trong cây con của nó. Hàm construct(A) xây dựng cây từ mảng A: nếu A rỗng -> null; chọn A[i] lớn nhất làm root; left = construct(A[0..i-1]); right = construct(A[i+1..n-1]). Cho root = construct(A). B là bản sao A thêm giá trị val (duy nhất). Xây dựng construct(B).
Ví dụ: val=5, cây đầu vào -> cây đầu ra.
Giải pháp đệ quy:
Hàm solve(root, val): nếu root null -> trả về node mới val.
Nếu root.val < val: tạo node mới val, left = root, trả về node mới.
Ngược lại: root->right = solve(root->right, val); trả về root.
Ví dụ hoàn chỉnh
#include <bits/stdc++.h>
using namespace std;
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;
}
void tree_level_trav(TreeNode* root) {
if (!root) return;
cout << "[";
queue<TreeNode*> q; q.push(root); q.push(NULL);
while (q.size() > 1) {
TreeNode* curr = q.front(); q.pop();
if (!curr) { q.push(NULL); }
else {
if (curr->left) q.push(curr->left);
if (curr->right) q.push(curr->right);
if (curr->val == 0) cout << "null, ";
else cout << curr->val << ", ";
}
}
cout << "]" << endl;
}
class Solution {
public:
TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
if (root->val < val) {
TreeNode* temp = new TreeNode(val);
temp->left = root;
return temp;
}
root->right = insertIntoMaxTree(root->right, val);
return root;
}
};
int main() {
vector<int> v = {4,1,3,NULL,NULL,2};
TreeNode* root = make_tree(v);
Solution ob;
tree_level_trav(ob.insertIntoMaxTree(root, 5));
}
Input
[4,1,3,null,null,2] 5
Output
[5, 4, 1, 3, null, null, 2, ]