本篇文章为你整理了每日算法之二叉搜索树与双向链表（搜索二叉树转双向链表）的详细内容，包含有二叉搜索树实现 搜索二叉树转双向链表 二叉树 二叉搜索树区别 二叉搜索树的定义 每日算法之二叉搜索树与双向链表，希望能帮助你了解 每日算法之二叉搜索树与双向链表。

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

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

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

　　4.你不用输出双向链表，程序会根据你的返回值自动打印输出

二叉树中序遍历除了递归方法，我们还可以尝试非递归解法，与常规的非递归中序遍历几乎相同，还是借助栈来辅助，只是增加了连接节点。

　　具体做法：

　　step 1：创建两个指针，一个指向题目中要求的链表头（head），一个指向当前遍历的前一节点（pre)，创建一个布尔型变量，标记是否是第一次到最左，因为第一次到最左就是链表头。

　　step 2：判断空树不能连接。

　　step 3：初始化一个栈辅助中序遍历。

　　step 4：依次将父节点加入栈中，直接进入二叉树最左端。

　　step 5：第一次进入最左，初始化head与pre，然后进入它的根节点开始连接。

　　step 6：最后将右子树加入栈中，栈中依次就弹出“左中右”的节点顺序，直到栈为空。

package mid.JZ36二叉搜索树与双向链表;

　　class TreeNode {

　　 int val = 0;

　　 TreeNode left = null;

　　 TreeNode right = null;

　　 public TreeNode(int val) {

　　 this.val = val;

　　public class Solution {

　　 //头节点

　　 private TreeNode head = null;

　　 //上一个节点

　　 private TreeNode pre = null;

　　 public TreeNode Convert(TreeNode pRootOfTree) {

　　 if (pRootOfTree == null) return null;

　　 //首先递归到最左最小值

　　 Convert(pRootOfTree.left);

　　 if (pre == null) {

　　 head = pRootOfTree;

　　 pre = pRootOfTree;

　　 } else {

　　 pRootOfTree.left = pre;

　　 pre.right = pRootOfTree;

　　 pre = pRootOfTree;

　　 //右递归

　　 Convert(pRootOfTree.right);

　　 return head;

　　以上就是每日算法之二叉搜索树与双向链表（搜索二叉树转双向链表）的详细内容，想要了解更多 每日算法之二叉搜索树与双向链表的内容，请持续关注盛行IT软件开发工作室。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。