378.二叉ルックアップツリーを二重チェーンテーブルに変換する

説明
二叉ルックアップツリーを中順に遍歴して双方向チェーンテーブルに変換します.
サンプル
2つのツリーを指定します.

        4
       / \
      2   5
     / \
    1   3

は、12345を返します.
構想

は、BSTの左、右サブツリーをそれぞれ双方向チェーンテーブル

に変換する.

は、BSTルートノードの値に等しいチェーンテーブルノードを新規に作成します.BSTであるため,newが出るノードはチェーンテーブルの中間に位置するはずであるため,左,右サブツリーから変換されたチェーンテーブルをそれぞれ接続する.このステップでは、左チェーンテーブルの末尾ノードと右チェーンテーブルのヘッダノード

を見つけます.

特殊状況の判別は、左チェーンテーブルまたは右チェーンテーブルが空である.そして、再帰出口が最後にチェーンヘッダノードに戻る

である.
コード#コード#

/**
 * 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;
 *     }
 * }
 */ 
 
//                    
class ResultType {
    DoublyListNode first, last;
    // first   last            
    public ResultType(DoublyListNode first, DoublyListNode last) {
        this.first = first;
        this.last = last;
    }
}

public class Solution {
    /**
     * @param root: The root of tree
     * @return: the head of doubly list node
     */
    public DoublyListNode bstToDoublyList(TreeNode root) {  
        if (root == null) {
            return null;
        }
        
        ResultType result = helper(root);
        return result.first;
    }
    
    // helper      ，                      
    public ResultType helper(TreeNode root) {  
        //     
        if (root == null) {
            return null;
        }
        
        ResultType left = helper(root.left);
        ResultType right = helper(root.right);
        
        //        node         
        DoublyListNode node = new DoublyListNode(root.val);
        
        // result           
        ResultType result = new ResultType(null, null);
        
        if (left == null) {
            result.first = node;
        //         ，           node     
        //             result
        } else {
            result.first = left.first;
            left.last.next = node;
            node.prev = left.last;
        }
        
        if (right == null) {
            result.last = node;
        //         ，           node     
        //             result
        } else {
            result.last = right.last;
            right.first.prev = node;
            node.next = right.first;
        }
        
        return result;
    }
}