剑指Offer系列-面试题27：二叉搜索树与双向链表

题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

思路：由二叉搜索树的原理，中序遍历即为有序的链表，因此直接中序遍历，一边遍历，一边调整指针。

代码：

/// 非递归，中序遍历 TreeNode* Convert(TreeNode* root) { if(root == NULL) { return NULL; } stack<TreeNode*> s; TreeNode* p = root; TreeNode* pre = NULL; bool first = true; while(p != NULL || !s.empty()) { while(p != NULL) { s.push(p); p = p->left; } p = s.top(); s.pop(); if(first) /// 只用一次 { root = p; pre = root; first = false; } else { pre->right = p; p->left = pre; pre = p; } p = p->right; } return root; }