劍指Offer面試題：25.二叉搜索樹與雙向鏈表
題目：輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。比如輸入下圖中左邊的二叉搜索樹，則輸出轉換之后的排序雙向鏈表。我們知道：在二叉樹中，每個結點都有兩個指向子結點的指針。在雙向鏈表中，每個結點也有兩個指針，它們分別指向前一個結點和后一個結點。由于這兩種結點的結構相似，同時二叉搜索樹也是一種排序的數據結構，因此在理論上有可能實現二叉搜索樹和排序的雙向鏈表的轉換。
一、題目：二叉搜索樹與雙向鏈表
題目：輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。比如輸入下圖中左邊的二叉搜索樹，則輸出轉換之后的排序雙向鏈表。
二叉搜索樹的節點定義如下，這里使用C#語言描述：
public class BinaryTreeNode { public int Data { get; set; } public BinaryTreeNode leftChild { get; set; } public BinaryTreeNode rightChild { get; set; } public BinaryTreeNode(int data) { this.Data = data; } public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right) { this.Data = data; this.leftChild = left; this.rightChild = right; } }
二、解題思路
2.1 核心步驟
首先，我們知道：在二叉樹中，每個結點都有兩個指向子結點的指針。在雙向鏈表中，每個結點也有兩個指針，它們分別指向前一個結點和后一個結點。
其次，由于要求轉換之后的鏈表是排好序的，我們可以中序遍歷樹中的每一個結點，這是因為中序遍歷算法的特點是按照從小到大的順序遍歷二叉樹的每一個結點。
最后，按照中序遍歷的順序，當我們遍歷轉換到根結點（值為10的結點）時，它的左子樹已經轉換成一個排序的鏈表了，并且處在鏈表中的最后一個結點是當前值最大的結點。我們把值為8的結點和根結點鏈接起來，此時鏈表中的最后一個結點就是10了。接著我們去遍歷轉換右子樹，并把根結點和右子樹中最小的結點鏈接起來。
很明顯，轉換它的左子樹和右子樹，由于遍歷和轉換過程是一樣的，很自然地想到可以用遞歸。
2.2 代碼實現
public BinaryTreeNode Convert(BinaryTreeNode root) { BinaryTreeNode lastNodeInList = null; ConvertNode(root, ref lastNodeInList); // lastNodeInList指向雙向鏈表的尾結點， // 我們需要返回頭結點 BinaryTreeNode headInList = lastNodeInList; while (headInList != null && headInList.leftChild != null) { headInList = headInList.leftChild; } return headInList; } private void ConvertNode(BinaryTreeNode node, ref BinaryTreeNode lastNodeInList) { if (node == null) { return; } BinaryTreeNode currentNode = node; // 轉換左子樹 if (currentNode.leftChild != null) { ConvertNode(currentNode.leftChild, ref lastNodeInList); } // 與根節點的銜接 currentNode.leftChild = lastNodeInList; if (lastNodeInList != null) { lastNodeInList.rightChild = currentNode; } lastNodeInList = currentNode; // 轉換右子樹 if (currentNode.rightChild != null) { ConvertNode(currentNode.rightChild, ref lastNodeInList); } }
三、單元測試
3.1 測試用例
（1）輔助方法的封裝
private void SetSubTreeNode(BinaryTreeNode root, BinaryTreeNode lChild, BinaryTreeNode rChild) { if (root == null) { return; } root.leftChild = lChild; root.rightChild = rChild; } private BSTConverter converter; [TestInitialize] public void Initialize() { converter = new BSTConverter(); } [TestCleanup] public void CleanUp() { converter = null; }
?。?）功能測試、特殊輸入測試
// 10 // / \ // 6 14 // /\ /\ // 4 8 12 16 [TestMethod] public void ConvertTest1() { BinaryTreeNode node10 = new BinaryTreeNode(10); BinaryTreeNode node6 = new BinaryTreeNode(6); BinaryTreeNode node4 = new BinaryTreeNode(4); BinaryTreeNode node8 = new BinaryTreeNode(8); BinaryTreeNode node14 = new BinaryTreeNode(14); BinaryTreeNode node12 = new BinaryTreeNode(12); BinaryTreeNode node16 = new BinaryTreeNode(16); SetSubTreeNode(node10, node6, node14); SetSubTreeNode(node6, node4, node8); SetSubTreeNode(node14, node12, node16); BinaryTreeNode result = converter.Convert(node10); Assert.AreEqual(result, node4); } // 5 // / // 4 // / // 3 // / // 2 // / // 1 [TestMethod] public void ConvertTest2() { BinaryTreeNode node5 = new BinaryTreeNode(5); BinaryTreeNode node4 = new BinaryTreeNode(4); BinaryTreeNode node3 = new BinaryTreeNode(3); BinaryTreeNode node2 = new BinaryTreeNode(2); BinaryTreeNode node1 = new BinaryTreeNode(1); node5.leftChild = node4; node4.leftChild = node3; node3.leftChild = node2; node2.leftChild = node1; BinaryTreeNode result = converter.Convert(node5); Assert.AreEqual(result, node1); } // 1 // \ // 2 // \ // 3 // \ // 4 // \ // 5 [TestMethod] public void ConvertTest3() { BinaryTreeNode node5 = new BinaryTreeNode(5); BinaryTreeNode node4 = new BinaryTreeNode(4); BinaryTreeNode node3 = new BinaryTreeNode(3); BinaryTreeNode node2 = new BinaryTreeNode(2); BinaryTreeNode node1 = new BinaryTreeNode(1); node1.rightChild = node2; node2.rightChild = node3; node3.rightChild = node4; node4.rightChild = node5; BinaryTreeNode result = converter.Convert(node1); Assert.AreEqual(result, node1); } // 樹中只有1個結點 [TestMethod] public void ConvertTest4() { BinaryTreeNode node1 = new BinaryTreeNode(1); BinaryTreeNode result = converter.Convert(node1); Assert.AreEqual(result, node1); } // 空指針 [TestMethod] public void ConvertTest5() { BinaryTreeNode result = converter.Convert(null); Assert.AreEqual(result, null); }
3.2 測試結果
?。?）測試通過情況
（2）代碼覆蓋率
浙公網安備 33010602011771號