剑指OFFER系列之36----二叉搜索树与双向链表

剑指OFFER

题目描述：输入一颗二叉搜索树，将该二叉搜索树转换为一个排序的双向链表。

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
#include<climits>

using namespace std;

struct TreeNode{
	int val;
	TreeNode* left;
	TreeNode* right;

	TreeNode(): val(-1), left(nullptr), right(nullptr){}
	TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};

void convertNode(TreeNode* root, TreeNode** biList){
	if(!root){
		return;
	}
	TreeNode* cur = root;
	if(cur -> left){
		convertNode(cur -> left, biList);
	}
	cur -> left = *biList;
	if(*biList){
		(*biList) -> right = cur;
	}
	*biList = cur;
	if(cur -> right){
		convertNode(cur -> right, biList);
	}
}

TreeNode* convert(TreeNode* root){
	TreeNode* biList = nullptr;
	convertNode(root, &biList);
	TreeNode* biHead = biList;
	while(biHead && biHead -> left){
		biHead = biHead -> left;
	}
	return biHead;
}

void buildTree(TreeNode* n1, TreeNode* n2, TreeNode* n3){
	if(n1){
		n1 -> left = n2;
		n1 -> right = n3;
	}
}

void showNode(TreeNode* node){
	if(!node){
		cout <<" -> null ";
	}else{
		if(node -> left){
			cout << node -> left -> val;
		}else{
			cout << "null ";
		}
		cout << " <- " << node -> val <<  " -> ";
		if(node -> right){
			cout <<  node -> right -> val;
		}else{
			cout << "null";
		}
	}
	cout << endl;
}

void showTree(TreeNode* root){
	showNode(root);
	if(root){
		if(root -> left){
			showNode(root -> left);
		}	
		if(root -> right){
			showNode(root -> right);
		}
	}
}

void showList(TreeNode* biHead){
	TreeNode* cur = biHead;
	cout << "from left to right: ";
	while(cur){
		cout << cur -> val << " -> ";
		if(!cur -> right){
			break;
		}
		cur = cur -> right;
	}
	cout << "null" << endl;
	cout << "from right to left: ";
	while(cur){
		cout << cur -> val << " -> ";
		if(!cur -> left){
			break;
		}
		cur = cur -> left;
	}
	cout<< "null" << endl;
}

void utils(){
	TreeNode* node1 = new TreeNode(10);
	TreeNode* node2 = new TreeNode(6);
	TreeNode* node3 = new TreeNode(14);
	TreeNode* node4 = new TreeNode(4);
	TreeNode* node5 = new TreeNode(8);
	TreeNode* node6 = new TreeNode(12);
	TreeNode* node7 = new TreeNode(16);

	buildTree(node1, node2, node3);
	buildTree(node2, node4, node5);
	buildTree(node3, node6, node7);
	
	cout << "input : " << endl;
	showTree(node1);

	cout << "output : " << endl;
	TreeNode* ans = convert(node1);
	showList(ans);
}

int main(){
	utils();
    return 0;
}