将二叉查找树转换成双链表

将一个二叉查找树按照中序遍历转换成双向链表。

样例

给定一个二叉查找树：



返回 1<->2<->3<->4<->5。

标签

链表

code

/**

 * Definition of TreeNode:

 * class TreeNode {

 * public:

 *     int val;

 *     TreeNode *left, *right;

 *     TreeNode(int val) {

 *         this->val = val;

 *         this->left = this->right = NULL;

 *     }

 * }

 * Definition of Doubly-ListNode

 * class DoublyListNode {

 * public:

 *     int val;

 *     DoublyListNode *next, *prev;

 *     DoublyListNode(int val) {

 *         this->val = val;

           this->prev = this->next = NULL;

 *     }

 * }

 */

class Solution {

public:

    /**

     * @param root: The root of tree

     * @return: the head of doubly list node

     */

    DoublyListNode* bstToDoublyList(TreeNode* root) {

        // Write your code here

        DoublyListNode* head=NULL;

        vector<int> list;

        if(root == NULL)

            return head;

        treeToList(root, list);

        head = listToDlist(list);

        return head;

    }

    void treeToList(TreeNode *TreeRoot, vector<int> &list) {

        if(TreeRoot != NULL) {

            treeToList(TreeRoot->left, list);

            list.push_back(TreeRoot->val);

            treeToList(TreeRoot->right, list);

        }

    }

    DoublyListNode* listToDlist(vector<int> &list) {

        DoublyListNode* head=NULL,* p=NULL,* q=NULL;

        int size = list.size();

        if(0 == size)

            return head;

        head = p = q = new DoublyListNode(list[0]);

        for(int i=1; i<size; i++) {

            p->next = new DoublyListNode(list[i]);

            p->next->prev = q;

            q = p->next;

            p = p->next;

        }

        return head;

    }

};