Convert Binary Search Tree to Doubly Linked List (Ladder)

Description

Convert a binary search tree to doubly linked list with in-order traversal.

Example
Given a binary search tree:

    4
   / \
  2   5
 / \
1   3

return 1<->2<->3<->4<->5

Link

Lintcode_ladder

Method

1. • create the data set [TreeNode*, previous node, next node]
   • then reaching leaf node, trying to connect current node to previous and next
   • For in-order traversal of BST, the seq is incresing/ascending
2. x

Example

1. 1

   /**
   * 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
        if (!root) {
            return nullptr;
        }
        DoublyListNode* tail = convert(root, nullptr, nullptr);
        while (tail->prev) {
            tail = tail->prev;
        }
        return tail;
    }
    DoublyListNode* convert(TreeNode* head, 
        DoublyListNode* prev, DoublyListNode* next
    ) {
        if (!head) {
            return nullptr;
        }
        DoublyListNode* node = new DoublyListNode(head->val);
        // in-order traversal
        // if left's child is valid
        // left child should be the prev of node
        if (head->left) {
            convert(head->left, prev, node);
        } else {
            node->prev = prev;
            if (prev) {
                prev->next = node;
            }
        }
        // if right's child is valid
        // right child should be the next of node
        if (head->right) {
            convert(head->right, node, next);
        } else {
            node->next = next;
            if (next) {
                next->prev = node;
            }
        }
        return node;
    }
   };
   

Similar problems

x

Tags

x