链接：https://pan.baidu.com/s/1THOtOUdQqBbrqfo6wgub_w 

提取码：ir2w 

 

1.把二元查找树转变成排序的双向链表

题目：

输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。

要求不能创建任何新的结点，只调整指针的指向。

10

/ \

6 14

/ \ / \

4 8 12 16

转换成双向链表

4=6=8=10=12=14=16。

首先我们定义的二元查找树节点的数据结构如下：

struct BSTreeNode

{

int m_nValue; // value of node

BSTreeNode m_pLeft; // left child of node

BSTreeNode m_pRight; // right child of node

};

ANSWER:

This is a traditional problem that can be solved using recursion.

For each node, connect the double linked lists created from left and right child node to form a full list.

/**

@param root The root node of the tree

@return The head node of the converted list.

/

BSTreeNode treeToLinkedList(BSTreeNode root) {

BSTreeNode head, * tail;

helper(head, tail, root);

return head;

}

void helper(BSTreeNode & head, BSTreeNode & tail, BSTreeNode root) {

BSTreeNode lt, *rh;

if (root == NULL) {

head = NULL, tail = NULL;

return;

}

helper(head, lt, root->m_pLeft);

helper(rh, tail, root->m_pRight);

if (lt!=NULL) {

lt->m_pRight = root;

root->m_pLeft = lt;

} else {

head = root;

}

if (rh!=NULL) {

root->m_pRight=rh;

rh->m_pLeft = root;

} else {

tail = root;

}

}

2.设计包含min 函数的栈。

定义栈的数据结构，要求添加一个min 函数，能够得到栈的最小元素。

要求函数min、push 以及pop 的时间复杂度都是O(1)。

ANSWER:

Stack is a LIFO data structure. When some element is popped from the stack, the status will recover to the original status as before that element was pushed. So we can recover the minimum element, too.

struct MinStackElement {

int data;

int min;

};

struct MinStack {

MinStackElement * data;

int size;

int top;

}

MinStack MinStackInit(int maxSize) {

MinStack stack;

stack.size = maxSize;

stack.data = (MinStackElement) malloc(sizeof(MinStackElement)maxSize);

stack.top = 0;

return stack;

}

void MinStackFree(MinStack stack) {

free(stack.data);

}

void MinStackPush(MinStack stack, int d) {

if (stack.top == stack.size) error(“out of stack space.”);

MinStackElement* p = stack.data[stack.top];

p->data = d;

p->min = (stack.top==0?d : stack.data[top-1]);

if (p->min > d) p->min = d;

top ++;

}