Leetcode 897. Increasing Order Search Tree

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Increasing Order Search Tree

2. Solution

  • Version 1
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
/**
* 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) {
if(!root) {
return root;
}
vector<TreeNode*> nodes;
inorder(root, nodes);
for(int i = 0; i < nodes.size() - 1; i++) {
nodes[i]->right = nodes[i + 1];
}
return nodes[0];
}
void inorder(TreeNode* root, vector<TreeNode*>& nodes) {
if(!root) {
return;
}
inorder(root->left, nodes);
root->left = nullptr;
nodes.push_back(root);
inorder(root->right, nodes);
}
};
  • Version 2
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
/**
* 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) {
if(!root) {
return root;
}
TreeNode* head = new TreeNode(0);
TreeNode* current = head;
inorder(root, current);
return head->right;
}
void inorder(TreeNode* root, TreeNode* current) {
if(!root) {
return;
}
inorder(root->left);
root->left = nullptr;
current->right = root;
current = root;
inorder(root->right);
}
};

Reference

  1. https://leetcode.com/problems/increasing-order-search-tree/description/
如果有收获,可以请我喝杯咖啡!