纯技术帖-说一些自己想了蛮久的题

1. How to determine whether a binary tree is left-complete? 就是每一层的node都fill满,最后一层的从左到右fill满.

此题看上去蛮简单,想了好一会, 附上code:


bool isPerfect(BT *root){
  if (root == NULL)
    return true;
  int height = maxHeight(root);
  //int numOfNodes = 2 ^ (height+1) - 1;
  int numOfNodes = pow(2, height) - 1;  //edited in 4/4/2012
  int count = 0;
  queue<BT *> q;
  q.push(root);
  count += 1;
  while(!q.empty()){
    BT *cur = q.front();
    q.pop();
    if (cur -> left != NULL){
      q.push(cur -> left);
      count += 1;
    }
    if (cur -> right != NULL){
      q.push(cur -> right);
      count += 1;
    }
  }
  if (count == numOfNodes)
    return true;
  else
    return false;
}//takes O(n) get height and O(n) to do the count



bool isLeftComplete(BT *root){
  if (root == NULL)
    return true;
  if (isPerfect(root))
    return true;
  if (!isPerfect(root -> left) && !isPerfect(root -> right))
    return false;
  if (isPerfect(root -> left) && !isPerfect(root -> right)){
    if (maxHeight(root -> left) - maxHeight(root -> right) == 0){
      return isComplete(root -> right);
    }else{
      return false;
    }
  }
  if (!isPerfect(root -> left) && isPerfect(root -> right)){
    if (maxHeight(root -> left) - maxHeight(root -> right) == 1){
      return isComplete(root -> left);
    }else{
      return false;
    }
  }
  //another case -- edited 4/4/2012
 if (isPerfect(root -> left) && isPerfect(root -> right)){
    if(maxHeight(root -> left) - maxHeight(root -> right) == 1)
      return true;
    else
      return false;
  }
}

关于 isLeftComplete的时间复杂度,觉得是nlogn, 不知道只用BFS能否直接O(n)搞定.尝试了几种O(n)bfs办法,比较复杂.用到的空间比较多.

持续更新..
对isLeftComplete作了几处修改. 需要判断,root是不是perfect, 然后判断root的left right是不是perfect, 总共有5个判断.

2. 实现了如何copy一个linkedlist, 这个list除了有next node,还有一个random node pointer, 也就是:

typedef struct list{
  int data;
  struct list *next;
  struct list *random;
}Node;
random可以随便指向其他node.
要求: copy完整的list, 还要求不影响原来的list, 时间要求O( n). 附上code, 实现起来没觉得那么容易,还是花了点时间. 已经test.


//copy a linkedlist without the random next pointer
Node *copyList(Node *n){
  if (n == NULL)
    return NULL;
  Node *sub_copy = copyList(n -> next);
  Node *newNode = (Node *)malloc(sizeof(Node));
  if (newNode != NULL){
    newNode -> data = n -> data;
    newNode -> next = sub_copy;
    return newNode;
  }
}

//copy a linkedlist with the random pointer
//O(n) way
Node *altMergeList(Node *n1, Node *n2){
  if (n1 == NULL)
    return n2;
  if (n2 == NULL)
    return n1;
  Node *sub = altMergeList(n1 -> next, n2 -> next);
  n2 -> next = sub;
  n1 -> next = n2;
  return n1;
}

Node *addRandomLink(Node *n){
  if (n == NULL)
    return NULL;
  int count = 0;
  Node *prev = NULL;
  Node *cur = n;
  while (cur != NULL){
    if (count % 2 == 1){
      cur -> random = prev -> random -> next;  //add the link
    }
    prev = cur;
    cur = cur -> next;
    count += 1;
  }
  return n; //
}

Node *getTheCopy(Node *n){
  if (n == NULL)
    return NULL;
 
  vector<Node *> v;
  //get original list back
  Node *or_head = n;
  Node *or_cur = n;
  while(or_cur != NULL){
    v.push_back(or_cur -> next);
    Node *tt = or_cur -> next -> next;
    or_cur -> next = tt;
    or_cur = tt;
  }
  //get our copied list
  if(v.empty()){
    return NULL;
  }
  Node *head = v[0];
  int index;
  for(index = 0; index < v.size() - 1; index++){
    v[index] -> next = v[index+1];
  }
  v[index] -> next = NULL;

  return head;
}

Node *copyListWithRandom(Node *n){
  //to get a copy of n
  Node *n_cp = copyList(n);
  Node *n_alt = altMergeList(n,n_cp);
  Node *n_r = addRandomLink(n_alt);
  Node *n_result = getTheCopy(n_r);
  return n_result;
}