二叉搜索树与双向链表
第二十五题:二叉搜索树与双向链表
题目描述
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
思路:
二叉树的中序遍历(左 根 右)
解法一:递归
解法二:非递归
注意:
①实质上就是利用二叉树的中序遍历
②当然此题也可将中序遍历的顺序调换为 (右 中 左)来解
具体实现如下图所示:
具体实现代码如下(递归):
//递归的中序遍历解
public class Solution {
private TreeNode head;
private TreeNode realHead;
public TreeNode Convert(TreeNode pRootOfTree) {
ConvertSub(pRootOfTree);
return realHead;
}
public void ConvertSub(TreeNode pRootOfTree) {
if (pRootOfTree == null){
return;
}
//左
ConvertSub(pRootOfTree.left);
if (head == null){
head = realHead = pRootOfTree;
}else {
//连接操作
head.right = pRootOfTree;
pRootOfTree.left = head;
head = pRootOfTree;
}
//右
ConvertSub(pRootOfTree.right);
}
}
非递归的中序遍历实现如下图所示:
具体实现代码如下(递归):
//非递归的中序遍历解
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null){
return pRootOfTree;
}
//返回的头结点
TreeNode list = null;
//用于记录栈弹出的上一个节点,用于过渡
TreeNode cur = null;
Stack<TreeNode> s = new Stack<>();
while(pRootOfTree != null || !s.isEmpty()){
if(pRootOfTree != null) {
s.push(pRootOfTree);
//一路向左
pRootOfTree = pRootOfTree.left;
} else {
pRootOfTree = s.pop();
//说明走到了最左的结点
if(list == null)
list = cur = pRootOfTree;
else {
//做连接操作
cur.right = pRootOfTree;
pRootOfTree.left = cur;
cur = pRootOfTree;
}
pRootOfTree = pRootOfTree.right;
}
}
return list;
}
}