題目

輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的節點，只能調整樹中節點指針的指向。比如，輸入下圖中的二叉搜索樹，輸出轉換之后的排序雙向鏈表。

二叉樹節點的定義如下：

public static class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int x) { val = x; }
}

分析

眾所周知，中序遍歷二叉搜索樹會得到有序的序列，我們目標是在中序遍歷二叉搜索樹過程中，逐步將其轉換成有序的雙向鏈表。另外，將樹節點的左子樹指針轉換成雙向鏈表節點的前驅指針，而樹節點的右子樹指針轉換成雙向鏈表節點的后驅指針。

放碼

import com.lun.util.BinaryTree.TreeNode;public class ConvertBSTToLinkedList {private TreeNode last;//用于指向雙向鏈表的尾節點public TreeNode convert(TreeNode root) {convertNode(root);TreeNode head = last;while(head != null && head.left != null) {head = head.left;}return head;}private void convertNode(TreeNode node) {if(node == null) {return;}TreeNode current = node;if(current.left != null) {convertNode(current.left);}current.left = last;//1.執行到這步，左子樹已經轉換成有序雙向鏈表if(last != null) {last.right = current;//2.}last = current;//3.current轉換成有序雙向鏈表的新尾節點if(current.right != null) {convertNode(current.right);}}}

測試

import org.junit.Assert;
import org.junit.Test;import com.lun.util.BinaryTree;
import com.lun.util.BinaryTree.TreeNode;public class ConvertBSTToLinkedListTest {@Testpublic void test() {ConvertBSTToLinkedList cbl = new ConvertBSTToLinkedList();TreeNode root = makeABST();TreeNode head = cbl.convert(root);Assert.assertEquals("4 -> 6 -> 8 -> 10 -> 12 -> 14 -> 16 -> \n" + "16 -> 14 -> 12 -> 10 -> 8 -> 6 -> 4 -> ", printList(head));}private TreeNode makeABST() {int[] array = {10, 6, 14, 4, 8, 12, 16};return BinaryTree.integerArray2BinarySearchTree(array);}private String printList(TreeNode head) {String result = "";TreeNode p = head;while(true) {result += (p.val + " -> ");if(p.right == null) {break;}p = p.right;}result += "\n";while(p != null) {result = result +  p.val + " -> ";p = p.left;}return result;}}