描述

將一個二叉查找樹按照中序遍歷轉(zhuǎn)換成雙向鏈表。

樣例

給定一個二叉查找樹：

        4
       / \
      2   5
     / \
    1   3

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

思路

1. 分別將 BST 的左、右子樹轉(zhuǎn)換成雙向鏈表
2. 新建出一個鏈表結(jié)點，值等于 BST 根節(jié)點的值。由于是 BST，所以 new 出的結(jié)點應(yīng)該位于鏈表的中間，所以分別連接左、右子樹轉(zhuǎn)換成的鏈表。這一步要找到左鏈表的尾結(jié)點和右鏈表的頭結(jié)點
3. 特殊情況的判別，左鏈表或右鏈表為空；以及遞歸出口
   最后返回鏈表頭結(jié)點即可

代碼

/**
 * 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;
 *     }
 * }
 */ 
 
// 首先的前提是二叉樹本身已經(jīng)是二叉查找樹
class ResultType {
    DoublyListNode first, last;
    // first 和 last 代表一段鏈表的頭尾結(jié)點
    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 函數(shù)的作用，計算出一顆二叉樹按中序遍歷形成鏈表的頭尾結(jié)點
    public ResultType helper(TreeNode root) {  
        // 遞歸出口
        if (root == null) {
            return null;
        }
        
        ResultType left = helper(root.left);
        ResultType right = helper(root.right);
        
        // 新建一個結(jié)點 node 值等于根結(jié)點的值
        DoublyListNode node = new DoublyListNode(root.val);
        
        // result 用于存儲鏈表最終結(jié)果
        ResultType result = new ResultType(null, null);
        
        if (left == null) {
            result.first = node;
        // 如果左子樹不為空，將左子樹的最右結(jié)點和 node 雙向連接
        // 左子樹形成的鏈表添加到 result
        } else {
            result.first = left.first;
            left.last.next = node;
            node.prev = left.last;
        }
        
        if (right == null) {
            result.last = node;
        // 如果右子樹不為空，將右子樹的最左結(jié)點和 node 雙向連接
        // 右子樹形成的鏈表添加到 result
        } else {
            result.last = right.last;
            right.first.prev = node;
            node.next = right.first;
        }
        
        return result;
    }
}