최대 트리의 루트 노드가 있다고 가정합니다. 최대 트리는 모든 노드가 하위 트리의 다른 값보다 큰 값을 갖는 트리입니다. 구성()이라는 메서드가 있다고 가정합니다. 이것은 목록 A에서 루트를 구성할 수 있습니다. 구성() 메서드는 다음과 같습니다. -
-
목록 A가 비어 있으면 null을 반환합니다.
-
그렇지 않으면 A[i]를 목록 A의 가장 큰 요소로 둡니다. 그런 다음 값이 A[i]인 루트 노드를 만듭니다.
-
루트의 왼쪽 자식은 구성([A[0], A[1], ..., A[i-1]])
이 됩니다. -
루트의 오른쪽 자식은 다음과 같습니다. 생성자([A[i+1], A[i+2], ..., A[n - 1]]) [n은 A의 길이입니다]
-
루트를 반환합니다.
A가 직접 주어지지 않았으며 루트 노드 루트 =구성(A)만 주어졌습니다. 이제 B가 val 값이 추가된 A의 복사본이라고 가정합니다. B는 고유한 값을 가집니다. (B)를 구성해야 합니다. 값이 5이고 입력 트리가 -
와 같은 경우
출력 트리는 다음과 같습니다 -
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
하나의 재귀 메서드 solve()를 정의합니다. 이것은 뿌리를 내리고 있습니다.
-
트리가 비어 있으면 값이 val인 새 노드를 만들고 해당 노드를 반환합니다.
-
루트 값
-
temp :=값이 val인 새 노드
-
임시의 왼쪽 :=루트
-
반환 온도
-
-
루트 오른쪽 :=해결(루트 오른쪽, val)
-
루트 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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 == NULL) return; cout << "["; queue<TreeNode *> q; TreeNode *curr; q.push(root); q.push(NULL); while (q.size() > 1) { curr = q.front(); q.pop(); if (curr == NULL){ q.push(NULL); } else { if(curr->left) q.push(curr->left); if(curr->right) q.push(curr->right); if(curr == NULL || 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; } }; main(){ vector<int> v = {4,1,3,NULL,NULL,2}; TreeNode *root = make_tree(v); Solution ob; tree_level_trav(ob.insertIntoMaxTree(root, 5)); }
입력
[4,1,3,null,null,2] 5
출력
[5, 4, 1, 3, null, null, 2, ]