Ｎ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;}//更新prev；prev = 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;}
};