菜鸡的算法修炼——二叉搜索树（二叉搜索树与双向链表）
题目描述(引自剑指offer)
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
菜鸡与大佬的对话
菜鸡修炼坊
| 数据结构 | 定义 |
树 | 树是由n（n>=0）个有限节点组成一个具有层次关系的集合。满足以下特点： ①每个元素称为结点； ②没有父结点的结点称为根结点； ③除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T0，T1，T2，……，Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树。 |
| 二叉树 | 二叉树是每个结点最多有两个子树的树结构。 |
二叉搜索树 | 二叉搜索树，它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。 |
题目分析
在了解二叉搜索树的定义之后，菜鸡觉得可以用递归和非递归两种方式来解决。首先考虑递归的方式，首先一个结点的引用标记，然后按照右子树，根，左子树的顺序进行遍历，在遍历的过程中调整指针的指向，并移动引用标记，最后就能得到排序的双向链表，标记引用的就是双向链表的头结点（最小结点）。其次考虑非递归的方式，同样的原理，只不过需要借助栈的数据结构来进行操作。菜鸡理顺思路之后，决定用Java代码实现他的心路历程。
代码实现
// 树的定义public class TreeNode {int value = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int value) {this.value = value;}}
public class Solution {// 定义结点引用标记TreeNode result = null;// 递归解决方案public TreeNode convertByRecursion(TreeNode root) {// 递归出口if(root == null) return root;// 递归遍历右子树convertByRecursion(root.right);// 找到最右结点，设置引用标记if(result == null){result = root;}// 非最右结点，调整指针指向，并移动引用标记，逐步串起整个链表else {result.left = root;root.right = result;result = root;}// 递归遍历左子树convertByRecursion(root.left);// 返回链表头结点（最小结点）的引用return result;}}
import java.util.Stack;public class Solution {// 非递归解决方案public TreeNode convertByNonRecursion(TreeNode root) {// 空树直接返回if(root == null) return root;// 定义结点引用标记TreeNode result = null;// 申请辅助栈Stack<TreeNode> stack = new Stack<>();while(root != null || !stack.isEmpty()){// 遍历右子树if(root != null) {stack.push(root);root = root.right;}else {root = stack.pop();// 找到最右结点，设置引用标记if(result == null) {result = root;}// 非最右结点，调整指针指向，并移动引用标记，逐步串起整个链表else {result.left = root;root.right = result;result = root;}// 遍历左子树root = root.left;}}// 返回链表头结点（最小结点）的引用return result;}}
经过这次修炼，菜鸡对树型结构有了一定的了解，菜鸡发现像链表，树这样递归定义的数据结构，在很多问题上都可以考虑递归的方式去解决。另外，菜鸡还掌握了二叉搜索树的特性，他发现，二叉搜索树在平面上的投影，其实就是有序的线性表。菜鸡越发体会到了基础知识的重要性，也越发体会到活学活用的重要性。菜鸡隐隐察觉到，修炼的终极产物是思想……