题目描述

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

分析

如果是这样一棵二叉搜索树：

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;}