LintCode-378.将二叉查找树转换成双链表

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

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

样例

给定一个二叉查找树：

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