Compression BST

Given an BST,  each node has two data(one is its data, another is the number of subtree nodes). convert the tree to another BST by replacing the second data(number of subtree nodes) with previous node data in inorder traversal. 要求in-place

中序遍历，并且改指针指向就行了。

类似的面试题，比如先序后序serialize BTree in place.

nooneknow 发表于 2012-11-5 04:54
中序遍历，并且改指针指向就行了。

类似的面试题，比如先序后序serialize BTree in place.

贴个code上来吧？ 斑竹大神~ 感觉这里面要考虑东西很多，之前各种写不对。。

我自己写的不知道对不对。
binaryTree *compress(binaryTree *root, int *prevdata, binaryTree **prevnode){
    if(!root) return NULL;
        int threshold =0;
        root->left = compress(root->left, prevdata, prevnode);
        if(*prevdata == INT_MIN){
               
            *prevdata = root->data;
                *prevnode = root;
                if(!root->right&&root->data!=mymax)
                        return NULL;;
        }else{
                if((*prevnode)->data2<root->data2){
                        root->data2 = *prevdata;
                        delete *prevnode;
                }
                else{
                        int temp = (*prevnode)->data;
                       
            (*prevnode)->data = root->data;
                        (*prevnode)->data2 = temp;
                    threshold =1;
                }
                *prevdata = INT_MIN;
        }
       
        root->right = compress(root->right,prevdata,prevnode);
        if(threshold == 1 && !root->right) {
            return NULL;   
        }else if(threshold ==1 && root->right)
                return root->right;
        return root;
}

binaryTree * makecompress(binaryTree *root){
    int p = INT_MIN;
        int *prevdata = &p;
        binaryTree **prevnode = NULL;
        prevnode = (binaryTree **)malloc(sizeof(binaryTree *));
        root = compress(root, prevdata, prevnode);
    return root;
}