广元建设机械网站,视觉传播设计与制作,营销型网站的作用是,昆明市网络优化案例文章目录#xff2e;iuke:JZ36.二叉树与双向链表题目描述示例思路分析代码实现#xff2e;iuke:JZ36.二叉树与双向链表
题目描述
描述 输入一棵二叉搜索树#xff0c;将该二叉搜索树转换成一个排序的双向链表。如下图所示 注意: 1.要求不能创建任何新的结点#xff0c;只…
文章目录iuke:JZ36.二叉树与双向链表题目描述示例思路分析代码实现iuke:JZ36.二叉树与双向链表
题目描述
描述 输入一棵二叉搜索树将该二叉搜索树转换成一个排序的双向链表。如下图所示 注意: 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 树的形状如上图 思路分析
1: 通过中序遍历,让先递归的结点在后递归的前面,每次左递归之后将prev与当前结点root的左指针指向上一层函数栈帧递归的结点,让上一层函数栈帧树结点的右指针指向当前结点,故而在每一层递归时应该保存当前结点的 位置. 2: 当将二叉树连接成双向链表后,此时的pRootOfTree依旧指向树的根结点,此时应该将pRootOfTree指向双向链表表头. 注意: 1: 在对指针进行访问的时候一定要考虑指针不为空的情况. 2: 为了回溯时让上一层的prev依旧有效,此时的形参prev最好用引用. 3: 当第一层中序递归遍历结束,编译器会主动返回到上一层函数栈帧,也就是中序遍历该开始的地方.
代码实现
class Solution {
public:void InorderConvert( TreeNode* cur,TreeNode* prev ){if( cur nullptr )return;//如果不是空就先往左子树遍历。InorderConvert(cur-left,prev);//走到这第一个结点就为4.cur-left prev;if( prev ){//执行这一步时prev不能指向空。prev-right cur;}//更新prevprev cur; InorderConvert( cur-right,prev);}TreeNode* Convert(TreeNode* pRootOfTree) {TreeNode* prev nullptr;InorderConvert(pRootOfTree,prev);//题目要求返回链表的头。TreeNode* head pRootOfTree;if( head){while( head-left ){head head-left;}}return head;}
};
