二叉树静态链表,二叉搜索树转双向链表

　　BM30二叉查找树和双向链表

　　分而治之知识点

　　描述一个二叉查找树，并将二叉查找树转换成一个有序双向链表。如下图所示

　　数据范围：输入二叉树中的节点数以及二叉树中每个节点的值。

　　需求：空间复杂度(即在原始树上操作)，时间复杂度

　　注：1。不需要创建任何新的节点，但是需要调整树中节点的指针。转换完成后，树中节点的左指针需要指向前任，树中节点的右指针需要指向继任者。

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

　　3.函数返回的TreeNode有左右指针，实际上可以看作是一个双向链表的数据结构。4.不需要输出双向链表，程序会根据你的返回值自动打印输出。

　　描述：二叉树的根节点

　　返回值描述：双向链表的头节点之一。

　　示例1输入：

　　{10，6，14，4，8，12，16}复制返回值：

　　从左到右依次是：4、6、8、10、12、14、16；从右到左依次是：16，14，12，10，8，6，4；复制描述：

　　进入主题图中的二叉树，输出时返回双向链表的头节点。2示例输入：

　　{5，4，#，3，#，2，#，1}复制返回值：

　　从左到右依次是：1，2，3，4，5；从右到左依次是：5，4，3，2，1；复制描述：

　　五

　　/

　　四

　　/

　　三

　　/

　　2

　　/

　　一个

　　树的形状如上图所示。

　　要将一棵搜索树转换成一个有序的双向链表，只需要按照中序遍历将链表串联起来即可。在串行连接的过程中，左边的节点代表双向链表的前一个节点，右边的节点代表双向链表的后一个节点，最后返回到最左边的节点。

　　解释：

　　为什么可以在遍历的过程中直接改变当前节点左边节点的指向？或者为什么可以直接改变当前驱动点右节点的点？

　　答案是肯定的，因为在中序遍历的时候，如果当前节点有左节点，那么在访问当前节点的时候，它的左节点一定已经被访问过了，所以没有必要再访问一次。在中序遍历过程中，一个节点的前任节点要么是它的左节点，要么是它的父节点。如果前任节点是其左节点，则左节点及其所有子节点都被访问过，可以直接修改指向。如果是其父节点，当前节点正好是其父节点的右节点，直接修改不会有问题。

　　实现如下：

　　#包含位/标准数据。h

　　//https://www . now coder . com/practice/947 f 6 EB 80d 944 a 84850 b 0538 BF 0 EC 3 a 5？tpId=295 tags=title=难度=0判断状态=0 rp=0来源URL=/考试/oj

　　定义树结构

　　{

　　int val

　　struct TreeNode * left

　　struct TreeNode * right

　　TreeNode(int x) : val(x)，left(nullptr)，right(nullptr) {}

　　};

　　TreeNode * Convert(TreeNode * pRootOfTree)

　　{

　　TreeNode * head=nullptr

　　TreeNode * pre _ node=nullptr

　　if (pRootOfTree==nullptr)

　　{

　　回程头；

　　}

　　STD:stack TreeNode * s；

　　auto node=pRootOfTree

　　while(节点！=nullptr ！s.empty()

　　{

　　while(节点！=nullptr)

　　{

　　s.push(节点)；

　　node=节点-左侧；

　　}

　　如果(！s.empty()

　　{

　　node=s . top()；

　　s . pop()；

　　If (head==nullptr)//head为空，表示当前节点是我们要找的链表的头节点。

　　{

　　头=节点；

　　pre_node=节点；

　　}

　　Else //否则，将当前节点和前任节点串联起来，然后将前任节点更新为当前节点。

　　{

　　pre_node- right=节点；

　　node- left=前置_节点；

　　pre_node=节点；

　　}

　　node=节点右；//再次遍历当前节点的右节点作为根节点。如果为空，则取队列的第一个元素。如果不为空，则将所有左边的节点以右边的节点为根进行排队。

　　}

　　}

　　回程头；

　　}

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