897. Increasing Order Search Tree - easy
문제
Given a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.
제한사항
- The number of nodes in the given tree will be between 1 and 100.
- Each node will have a unique integer value from 0 to 1000.
입출력 예
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Example 1:
Input: [5,3,6,2,4,null,8,1,null,null,null,7,9]
5
/ \
3 6
/ \ \
2 4 8
/ / \
1 7 9
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
1
\
2
\
3
\
4
\
5
\
6
\
7
\
8
\
9
풀이
- Tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* increasingBST(TreeNode* root) {
vector<int> item;
// inorder로 값 검색
inorder(root, item);
// 새로운 트리 생성후 저장한 값 지정
TreeNode* node = new TreeNode(0);
TreeNode* head = node;
for(const auto& i : item){
head->right = new TreeNode(i);
head = head->right;
}
return node->right;
}
// 트리 inorder 탐색
void inorder(TreeNode* root, vector<int>& item){
if(root == nullptr)
return;
inorder(root->left, item);
item.push_back(root->val);
inorder(root->right, item);
}
};