二叉搜索树转化成双向链表

2018-08-28sad creeper

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */

function Convert(pRootOfTree)
{
if(!pRootOfTree)
return ;
var pre = null;
ConvertHelper(pRootOfTree);
let result = pRootOfTree;
while(result.left){
result = result.left
}
return result;
function ConvertHelper(pRootOfTree){
if(!pRootOfTree)
return ;

ConvertHelper(pRootOfTree.left);

pRootOfTree.left = pre;
if(pre){
pre.right = pRootOfTree;
}
pre = pRootOfTree;

ConvertHelper(pRootOfTree.right);
}
}

//使用中序遍历即是从小到大遍历,然后在遍历过程中使用一个变量 pre 保存前一个节点,并在遍历过程中改变链接即可

阅读 93 评论