题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
分析
如果是这样一棵二叉搜索树：
那么它对应的双向链表顺序为：
1 3 4 5 7 10 11 15 复制代码
仔细观察发现这个序列和树的中序遍历是一样的，所以算法就好写了，先中序遍历得到一个序列，然后再按照双向链表的指针规则链接起来即可。
代码实现
/* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ function Convert(r) { if(r === null) return r; var q = [], s = []; var cur = r; while(cur !== null || s.length !== 0) { if(cur !== null){ s.push(cur); cur = cur.left; }else{ cur = s.pop(); q.push(cur); cur = cur.right; } } r = q.shift(); r.left = null; r.right = null; var tail = r; cur = null; while(q.length !== 0){ cur = q.shift(); tail.right = cur; cur.left = tail; tail = cur; } return r; }
