897. Increasing Order Search Tree

發表於 | 分類於

problem

solution

option 1 - extra space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> vec;
    void preorder(TreeNode *root){
        if(!root) return;
        preorder(root->left);
        vec.push_back(root->val);
        preorder(root->right);
    }
    TreeNode* increasingBST(TreeNode* root) {
        preorder(root);
        TreeNode *p = new TreeNode(-1), *ans = p;
        for(int val:vec){
            p->right = new TreeNode(val);
            p=p->right;
        }
        return ans->right;
        
    }
};

option 2 - without extra space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    TreeNode * p = new TreeNode(-1);
    void preorder(TreeNode *root){
        if(!root) return;
        TreeNode *left = root->left;
        TreeNode *right = root->right;
        root->left = nullptr;
        root->right = nullptr;
        
        preorder(left);
        
        p->right = root;
        p=p->right;
        preorder(right);
        
    }
    TreeNode* increasingBST(TreeNode* root) {
        TreeNode *ans = p;;
        preorder(root);
        return ans->right;
        
    }
};