导语：剑指offer(二十六)-二叉搜索树与双向链表(Java版)

描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

注意:

1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继

2.返回链表中的第一个节点的指针

3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构

4.你不用输出或者处理，示例中输出里面的英文，比如这样的，程序会根据你的返回值自动打印输出

示例:

输入: {10,6,14,4,8,12,16}

输出:From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;

解析:

输入就是一棵二叉树，如上图，输出的时候会将这个双向链表从左到右输出，以及

从右到左输出，确保答案的正确

第一种解法，双向链表中，每个节点是有两个指针的，分别是指向后一个节点和指向前一个节点，在二叉搜索树中，左节点的值永远小于父节点的值，而右节点的值永远大于父节点的值，对于我们来说，在转换的时候，最开始二叉搜索树中指向左节点的 指针调整为链表中指向前一个节点的指针，而原先指向右节点的指针调整为指向链表中指向后一个节点的指针，对于二叉树来说，中序遍历（左节点->根节点->右节点）已经将一颗二叉搜索树转换为了一个单向的链表，而我们要做的就是在中序遍历的时候，加上右指针，使用递归代码如下

TreeNode head = null;//链表头TreeNode listHead = null;public TreeNode firstConvert(TreeNode pRootOfTree) {    if(null == pRootOfTree){        return null;    }    firstConvert(pRootOfTree.left);    if(null == head){        head = pRootOfTree;        listHead = pRootOfTree;    }else {        head.right = pRootOfTree;        pRootOfTree.left = head;        head = pRootOfTree;    }    firstConvert(pRootOfTree.right);    return listHead;}

第二种解法，不使用递归，采用一个栈来实现，代码如下

public TreeNode secondConvert(TreeNode pRootOfTree) {    if(null == pRootOfTree){        return null;    }    TreeNode head = null;    TreeNode pre = null;    Stack<TreeNode> treeNodes = new Stack<>();    while (null != pRootOfTree || !treeNodes.isEmpty()){        while (null != pRootOfTree){            treeNodes.push(pRootOfTree);            pRootOfTree = pRootOfTree.left;        }        TreeNode pop = treeNodes.pop();        if(head == null){            head = pop;            pre = pop;        }else {            pre.right = pop;            pop.left = pre;            pre = pop;        }        pRootOfTree = pop.right;    }    return  head;}

免责声明:本站部份内容由优秀作者和原创用户编辑投稿，本站仅提供存储服务，不拥有所有权,不承担法律责任。若涉嫌侵权/违法的，请反馈，一经查实立刻删除内容。本文内容由快快网络小楠创作整理编辑！