【剑指offer-C++】JZ36：二叉搜索树与双向链表

• • 题目描述
  • 解题思路

题目描述

描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示：

数据范围：输入二叉树的节点数 0≤n≤1000，二叉树中每个节点的值 0≤val≤1000。

要求：空间复杂度O(1)（即在原树上操作），时间复杂度O(n)。

注意:
1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继；
2.返回链表中的第一个节点的指针；
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构；
4.你不用输出双向链表，程序会根据你的返回值自动打印输出；

输入描述：二叉树的根节点。
返回值描述：双向链表的其中一个头节点。

输入：{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;
说明：输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。 

输入：{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
树的形状如上图     

解题思路

二叉搜索树与双向链表：最直观的想法是，中序遍历二叉搜索树，并使用一个数组保存中序遍历的结点指针结果，再遍历中序数组将其左右相连，最后返回中序遍历数组的第一个元素即可。

vector TreeList; //中序遍历数组
//中序遍历 得到中序遍历数组
void dfs(TreeNode* cur)
{if(!cur)return;dfs(cur->left);TreeList.push_back(cur);dfs(cur->right);
}
TreeNode* Convert(TreeNode* pRootOfTree) 
{if(!pRootOfTree) //空树return nullptr;dfs(pRootOfTree);for(int i=0;iTreeList[i]->right=TreeList[i+1];TreeList[i+1]->left=TreeList[i];}return TreeList[0];
}

优化：上述方法开辟了额外的数组存储空间，那么有没有什么原地操作的方法呢？当然有！使用二叉树双指针即可！其中使用一个指针pre表示前驱结点，使用一个指针cur表示当前结点，仍然使用中序遍历方法，当左子树遍历完成后，即肯定cur->left为空才返回，此时将cur->left设置为前驱节点，同时，如果pre不为空的话，当前节点必定为前驱节点的后继节点，即pre->right=cur，当然，也要更新前驱节点为当前结点，再继续右子树的遍历，最后返回二叉树的最左下即中序遍历的开头结点即可。(其实就是中序遍历，然后在处理中间结点时，其左边指向前驱，如果前驱不为空，那么前驱的后继就指向当前，这样就避免了再遍历一次来完成后继的填充，其与数组类似，只不过是将数组转化为了指针)

TreeNode *pre=nullptr;
//中序遍历 得到中序遍历数组
void dfs(TreeNode* cur)
{if(!cur) //叶子结点return;dfs(cur->left); //左子树遍历cur->left=pre;  //更新前驱if(pre) //更新后继pre->right=cur;pre=cur; //更新下一次的前驱dfs(cur->right);  //右子树遍历
}
TreeNode* Convert(TreeNode* pRootOfTree) 
{if(!pRootOfTree) //空树return nullptr;dfs(pRootOfTree); //中序遍历while(pRootOfTree->left) //找到最左下pRootOfTree=pRootOfTree->left;return pRootOfTree; //双向链表头结点
}

注意，是通过更新当前的左子树为前驱，同时当前驱不为空，来更新前驱的右子树为当前来实现双向奔赴的啊！！