[LintCode] 378 Convert Binary Search Tree to Doubly Linked List 解题报告

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



思路
in order就是左根右的顺序。
ResultType里我们存当前inorder双向链表的头和尾。
我们可以用Divide & Conquer的思想去做。
求出：
1：左子树的inorder的双向链表。
2：右子树的inorder的双向链表。
3：根就是用root.val做成一个单节点的双向链表。
以左 - 根 -右的顺序，把上面三个双向链表接起来。




Code

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 * Definition for Doubly-ListNode.
 * public class DoublyListNode {
 *     int val;
 *     DoublyListNode next, prev;
 *     DoublyListNode(int val) {
 *         this.val = val;
 *         this.next = this.prev = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param root: The root of tree
     * @return: the head of doubly list node
     */
    
    class ResultType {
        DoublyListNode head;
        DoublyListNode tail;
        public ResultType(DoublyListNode head, DoublyListNode tail1) {
            this.head = head;
            this.tail = tail;
        }
    }
    
    public DoublyListNode bstToDoublyList(TreeNode root) {  
        // Write your code here
        
        ResultType result = helper(root);
        return result.head;
    }
    
    public ResultType helper(TreeNode root) {
        if(root == null) {
            return new ResultType(null, null);
        }
        
        ResultType left = helper(root.left);
        ResultType right = helper(root.right);
        
        ResultType curr = new ResultType(null, null);
        DoublyListNode node = new DoublyListNode(root.val);
        
        if (left.head != null) {
            left.tail.next = node;
            node.prev = left.tail;
            curr.head = left.head;
        }
        else {
            curr.head = node;
        }
        
        if (right.head != null) {
            node.next = right.head;
            right.head.prev = node;
            curr.tail = right.tail;
        }
        else {
            curr.tail = node;
        }
        
        return curr;
    }
}