菜鸡的算法修炼：二叉搜索树（二叉搜索树与双向链表）

题目描述(引自剑指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;

}

}

经过这次修炼，菜鸡对树型结构有了一定的了解，菜鸡发现像链表，树这样递归定义的数据结构，在很多问题上都可以考虑递归的方式去解决。另外，菜鸡还掌握了二叉搜索树的特性，他发现，二叉搜索树在平面上的投影，其实就是有序的线性表。菜鸡越发体会到了基础知识的重要性，也越发体会到活学活用的重要性。菜鸡隐隐察觉到，修炼的终极产物是思想……