题目链接:
二叉搜索树与双向链表
思路1:
搜索二叉树转换成有序双向链表 = 左子树构建得双向有序链表+根节点+右子树构建得双向有序链表
用图分析:
代码:
public class Solution {
public TreeNode CreateList(TreeNode pCur){
if(pCur==null){
return null;
}
TreeNode leftTree = CreateList(pCur.left);//将左子树创建为双向链表
TreeNode rightTree = CreateList(pCur.right);//将左子树创建为双向链表
if(leftTree!=null){
while(leftTree.right!=null){//遍历找到左子树的最右边结点
leftTree=leftTree.right;
}
leftTree.right=pCur;
pCur.left=leftTree;
}
if(rightTree!=null){
while(rightTree.left!=null){//遍历找到右子树最左边的结点
rightTree=rightTree.left;
}
pCur.right=rightTree;
rightTree.left=pCur;
}
return pCur;
}
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null){
return null;
}
CreateList(pRootOfTree);
TreeNode head=pRootOfTree;
while(head.left!=null){
head=head.left;
}
return head;
}
}
在这里可以看到,并没有刻意去控制链表的头和尾的null,那是因为一棵用二叉搜索树创建的链表的头
节点的left
和
尾节点的right
自然而然是
null
。
思路2:
引入一个变量prev,用来记录pCur的前一个结点。
遍历的过程是中序遍历:pCur的顺序是中序遍历的顺序,prev的顺序也是中序遍历得顺序。
public class Solution {
TreeNode prev=null;//prev指向pCur的前一个结点
public void CreateList(TreeNode pCur){
if(pCur==null){
return;
}
CreateList(pCur.left);
pCur.left=prev;
if(prev!=null){
prev.right=pCur;
}
prev=pCur;//让prev指向当前结点
CreateList(pCur.right);
}
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null){
return null;
}
CreateList(pRootOfTree);
TreeNode head=pRootOfTree;
while(head.left!=null){
head=head.left;
}
return head;
}
}
版权声明:本文为qq_52276036原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。