河南省国基建设集团有限公司网站,googleseo是什么,巧家县城乡建设局网站,备案 网站名称 修改问题描述#xff1a;
输入一棵二叉搜索树#xff0c;将该二叉搜索树转换成一个排序的双向链表。
问题要求#xff1a;
1.要求不能创建任何新的结点#xff0c;只能调整树中结点指针的指向。当转化完成以后#xff0c;树中节点的左指 针需要指向前驱#xff0c;树中节点…问题描述
输入一棵二叉搜索树将该二叉搜索树转换成一个排序的双向链表。
问题要求
1.要求不能创建任何新的结点只能调整树中结点指针的指向。当转化完成以后树中节点的左指 针需要指向前驱树中节点的右指针需要指向后继。 2.返回链表中的第一个节点的指针。 3.函数返回的TreeNode有左右指针其实可以看成一个双向链表的数据结构。 4.你不用输出双向链表程序会根据你的返回值自动打印输出。
输出描述
如图所示 示例1
输入
{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;
说明
输入题面图中二叉树输出的时候将双向链表的头节点返回即可。
示例2
输入
{5,4,#,3,#,2,#,1}
返回值
From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1;
说明5/4/3/2/1
树的形状如上图 问题分析
将搜索二叉树转换成一个排序的双向链表从二叉树的性质可以知道其中序遍历对应的是有序的
所以形成的双向链表的顺序必须跟着搜索二叉树的中序遍历走这样才保证是有序的其次我们需
要将二叉树的左右指针当做双向链表的前后指针左为前右为后从而通过中序遍历来确定双向链
表。
问题实现
代码实现
class Solution {
public:void InOrder(TreeNode*cur,TreeNode* prev){if(cur nullptr){return;}InOrder(cur-left,prev);cur-left prev;if(prev){prev-right cur;}prev cur;InOrder(cur-right,prev);}TreeNode* Convert(TreeNode* pRootOfTree) {TreeNode* prev nullptr;InOrder(pRootOfTree, prev);TreeNode* head pRootOfTree;while(head head-left){head head-left;}return head;}
};
这就是对应的实现。
