C/C++面试题 – 把二元查找树变成排序的双向链表

#include "stdafx.h"

struct node
{
	node * left;
	node * right;
	int value;
};

void convert(node * root, node *& last)
{
	if(root == NULL)
		return;

	if(root->left)
		convert(root->left, last);

	root->left = last;

	if(last)
		last->right = root;

	last = root;

	if(root->right)
		convert(root->right, last);

}

node * solution(node * root)
{
	node * last = NULL;
	convert(root, last);

	while(last && last->left)
		last = last->left;

	return last;
}

int _tmain(int argc, _TCHAR* argv[])
{
	node * n1 = new node();
	node * n2 = new node();
	node * n3 = new node();
	node * n4 = new node();

	n1->left = n2;
	n1->right = n3;
	n1->value = 3;

	n2->left = n4;
	n2->right = NULL;
	n2->value = 2;

	n3->left = NULL;
	n3->right = NULL;
	n3->value = 4;

	n4->left = NULL;
	n4->right = NULL;
	n4->value = 1;

	node * n = solution(n1);
	while(n)
	{
		printf("%d ",n->value);
		n = n->right;
	}
	return 0;
}