2018/11/4
🍞环境:牛客的编译环境
🍰语言:JavaScript
☕️难点:
- 二叉搜索树的概念:二叉搜索树也叫二叉排序树,规则是所有比根节点小的数都是根节点的左子树中,所有比根节点大的数都是根节点的右子树。
- 开始不太明白将二叉搜索树变成双向链表的意思,根据搜索树的特点,比root节点小的树都在左边,比root节点大的数在右边,转换成双向链表的话,实际上就是指一个数字从小到大排序的双向链表。
🍊题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向
🍎思路:
先找到最左子树,记录该子树,在程序的最后返回该节点。
找到左子树后,按照二叉搜索树的特点,可以用pre节点去保存左边的节点,之后设置先后即可。
🍇代码:
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function Convert(pRootOfTree)
{
// write code here
if(pRootOfTree == null)
return null;
var stack = [],
p = pRootOfTree,
isFirst = true;
var pre;
var root;
while(p != null || stack.length > 0){
while(p != null){
stack.push(p);
p = p.left;
}
p = stack.pop();
if(isFirst){
root = p;
pre = root;
isFirst = false;
}else{
pre.right = p;
p.left = pre;
pre = p;
}
p = p.right;
}
return root;
}