菜鸡的算法修炼:二叉搜索树(二叉搜索树与双向链表)

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

}

}

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

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章