劍指Offer面試題：17.樹的子結構
題目：輸入兩棵二叉樹A和B，判斷B是不是A的子結構。例如下圖中的兩棵二叉樹，由于A中有一部分子樹的結構和B是一樣的，因此B是A的子結構。要查找樹A中是否存在和樹B結構一樣的子樹，我們可以分成兩步：Step1.在樹A中找到和B的根結點的值一樣的結點R；Step2.判斷樹A中以R為根結點的子樹是不是包含和樹B一樣的結構。很明顯，這是一個遞歸的過程。
一、題目：樹的子結構
題目：輸入兩棵二叉樹A和B，判斷B是不是A的子結構。例如下圖中的兩棵二叉樹，由于A中有一部分子樹的結構和B是一樣的，因此B是A的子結構。
該二叉樹的節點定義如下，這里使用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 核心步驟
要查找樹A中是否存在和樹B結構一樣的子樹，我們可以分成兩步：
Step1.在樹A中找到和B的根結點的值一樣的結點R；
Step2.判斷樹A中以R為根結點的子樹是不是包含和樹B一樣的結構。
很明顯，這是一個遞歸的過程。
2.2 代碼實現
public static bool HasSubTree(BinaryTreeNode root1, BinaryTreeNode root2) { bool result = false; if (root1 != null && root2 != null) { if (root1.Data == root2.Data) { result = DoesTree1HasTree2(root1, root2); } // 從根節點的左子樹開始匹配Tree2 if (!result) { result = HasSubTree(root1.leftChild, root2); } // 如果左子樹沒有匹配成功則繼續在右子樹中繼續匹配Tree2 if (!result) { result = HasSubTree(root1.rightChild, root2); } } return result; } private static bool DoesTree1HasTree2(BinaryTreeNode root1, BinaryTreeNode root2) { if (root2 == null) { // 證明Tree2已經遍歷結束，匹配成功 return true; } if (root1 == null) { // 證明Tree1已經遍歷結束，匹配失敗 return false; } if (root1.Data != root2.Data) { return false; } // 遞歸驗證左子樹和右子樹是否包含Tree2 return DoesTree1HasTree2(root1.leftChild, root2.leftChild) && DoesTree1HasTree2(root1.rightChild, root2.rightChild); }
三、單元測試
為了方便測試，這里封裝了一個設置指定根節點的左孩子和右孩子節點的方法：SetSubTreeNode
public void SetSubTreeNode(BinaryTreeNode root, BinaryTreeNode lChild, BinaryTreeNode rChild) { if (root == null) { return; } root.leftChild = lChild; root.rightChild = rChild; }
3.1 功能測試
// 01.樹中結點含有分叉，樹B是樹A的子結構 // 8 8 // / \ / \ // 8 7 9 2 // / \ // 9 2 // / \ // 4 7 [TestMethod] public void HasSubTreeTest1() { BinaryTreeNode nodeA1 = new BinaryTreeNode(8); BinaryTreeNode nodeA2 = new BinaryTreeNode(8); BinaryTreeNode nodeA3 = new BinaryTreeNode(7); BinaryTreeNode nodeA4 = new BinaryTreeNode(9); BinaryTreeNode nodeA5 = new BinaryTreeNode(2); BinaryTreeNode nodeA6 = new BinaryTreeNode(4); BinaryTreeNode nodeA7 = new BinaryTreeNode(7); SetSubTreeNode(nodeA1, nodeA2, nodeA3); SetSubTreeNode(nodeA2, nodeA4, nodeA5); SetSubTreeNode(nodeA5, nodeA6, nodeA7); BinaryTreeNode nodeB1 = new BinaryTreeNode(8); BinaryTreeNode nodeB2 = new BinaryTreeNode(9); BinaryTreeNode nodeB3 = new BinaryTreeNode(2); SetSubTreeNode(nodeB1, nodeB2, nodeB3); Assert.AreEqual(SubTreeHelper.HasSubTree(nodeA1, nodeB1), true); } // 02.樹中結點含有分叉，樹B不是樹A的子結構 // 8 8 // / \ / \ // 8 7 9 2 // / \ // 9 3 // / \ // 4 7 [TestMethod] public void HasSubTreeTest2() { BinaryTreeNode nodeA1 = new BinaryTreeNode(8); BinaryTreeNode nodeA2 = new BinaryTreeNode(8); BinaryTreeNode nodeA3 = new BinaryTreeNode(7); BinaryTreeNode nodeA4 = new BinaryTreeNode(9); BinaryTreeNode nodeA5 = new BinaryTreeNode(3); BinaryTreeNode nodeA6 = new BinaryTreeNode(4); BinaryTreeNode nodeA7 = new BinaryTreeNode(7); SetSubTreeNode(nodeA1, nodeA2, nodeA3); SetSubTreeNode(nodeA2, nodeA4, nodeA5); SetSubTreeNode(nodeA5, nodeA6, nodeA7); BinaryTreeNode nodeB1 = new BinaryTreeNode(8); BinaryTreeNode nodeB2 = new BinaryTreeNode(9); BinaryTreeNode nodeB3 = new BinaryTreeNode(2); SetSubTreeNode(nodeB1, nodeB2, nodeB3); Assert.AreEqual(SubTreeHelper.HasSubTree(nodeA1, nodeB1), false); }
3.2 特殊輸入測試
// 03.樹中結點只有左子結點，樹B是樹A的子結構 // 8 8 // / / // 8 9 // / / // 9 2 // / // 2 // / // 5 [TestMethod] public void HasSubTreeTest3() { BinaryTreeNode nodeA1 = new BinaryTreeNode(8); BinaryTreeNode nodeA2 = new BinaryTreeNode(8); BinaryTreeNode nodeA3 = new BinaryTreeNode(9); BinaryTreeNode nodeA4 = new BinaryTreeNode(2); BinaryTreeNode nodeA5 = new BinaryTreeNode(5); nodeA1.leftChild = nodeA2; nodeA2.leftChild = nodeA3; nodeA3.leftChild = nodeA4; nodeA4.leftChild = nodeA5; BinaryTreeNode nodeB1 = new BinaryTreeNode(8); BinaryTreeNode nodeB2 = new BinaryTreeNode(9); BinaryTreeNode nodeB3 = new BinaryTreeNode(2); nodeB1.leftChild = nodeB2; nodeB2.leftChild = nodeB3; Assert.AreEqual(SubTreeHelper.HasSubTree(nodeA1, nodeB1), true); } // 04.樹中結點只有左子結點，樹B不是樹A的子結構 // 8 8 // / / // 8 9 // / / // 9 3 // / // 2 // / // 5 [TestMethod] public void HasSubTreeTest4() { BinaryTreeNode nodeA1 = new BinaryTreeNode(8); BinaryTreeNode nodeA2 = new BinaryTreeNode(8); BinaryTreeNode nodeA3 = new BinaryTreeNode(9); BinaryTreeNode nodeA4 = new BinaryTreeNode(2); BinaryTreeNode nodeA5 = new BinaryTreeNode(5); nodeA1.leftChild = nodeA2; nodeA2.leftChild = nodeA3; nodeA3.leftChild = nodeA4; nodeA4.leftChild = nodeA5; BinaryTreeNode nodeB1 = new BinaryTreeNode(8); BinaryTreeNode nodeB2 = new BinaryTreeNode(9); BinaryTreeNode nodeB3 = new BinaryTreeNode(3); nodeB1.leftChild = nodeB2; nodeB2.leftChild = nodeB3; Assert.AreEqual(SubTreeHelper.HasSubTree(nodeA1, nodeB1), false); } // 05.樹中結點只有右子結點，樹B是樹A的子結構 // 8 8 // \ \ // 8 9 // \ \ // 9 2 // \ // 2 // \ // 5 [TestMethod] public void HasSubTreeTest5() { BinaryTreeNode nodeA1 = new BinaryTreeNode(8); BinaryTreeNode nodeA2 = new BinaryTreeNode(8); BinaryTreeNode nodeA3 = new BinaryTreeNode(9); BinaryTreeNode nodeA4 = new BinaryTreeNode(2); BinaryTreeNode nodeA5 = new BinaryTreeNode(5); nodeA1.rightChild = nodeA2; nodeA2.rightChild = nodeA3; nodeA3.rightChild = nodeA4; nodeA4.rightChild = nodeA5; BinaryTreeNode nodeB1 = new BinaryTreeNode(8); BinaryTreeNode nodeB2 = new BinaryTreeNode(9); BinaryTreeNode nodeB3 = new BinaryTreeNode(2); nodeB1.rightChild = nodeB2; nodeB2.rightChild = nodeB3; Assert.AreEqual(SubTreeHelper.HasSubTree(nodeA1, nodeB1), true); } // 06.樹中結點只有右子結點，樹B不是樹A的子結構 // 8 8 // \ \ // 8 9 // \ / \ // 9 3 2 // \ // 2 // \ // 5 [TestMethod] public void HasSubTreeTest6() { BinaryTreeNode nodeA1 = new BinaryTreeNode(8); BinaryTreeNode nodeA2 = new BinaryTreeNode(8); BinaryTreeNode nodeA3 = new BinaryTreeNode(9); BinaryTreeNode nodeA4 = new BinaryTreeNode(2); BinaryTreeNode nodeA5 = new BinaryTreeNode(5); nodeA1.rightChild = nodeA2; nodeA2.rightChild = nodeA3; nodeA3.rightChild = nodeA4; nodeA4.rightChild = nodeA5; BinaryTreeNode nodeB1 = new BinaryTreeNode(8); BinaryTreeNode nodeB2 = new BinaryTreeNode(9); BinaryTreeNode nodeB3 = new BinaryTreeNode(3); BinaryTreeNode nodeB4 = new BinaryTreeNode(2); nodeB1.rightChild = nodeB2; SetSubTreeNode(nodeB2, nodeB3, nodeB4); Assert.AreEqual(SubTreeHelper.HasSubTree(nodeA1, nodeB1), false); } // 07.樹A為空樹 [TestMethod] public void HasSubTreeTest7() { BinaryTreeNode nodeB1 = new BinaryTreeNode(8); BinaryTreeNode nodeB2 = new BinaryTreeNode(9); BinaryTreeNode nodeB3 = new BinaryTreeNode(3); BinaryTreeNode nodeB4 = new BinaryTreeNode(2); nodeB1.rightChild = nodeB2; SetSubTreeNode(nodeB2, nodeB3, nodeB4); Assert.AreEqual(SubTreeHelper.HasSubTree(null, nodeB1), false); } // 08.樹B為空樹 [TestMethod] public void HasSubTreeTest8() { BinaryTreeNode nodeA1 = new BinaryTreeNode(8); BinaryTreeNode nodeA2 = new BinaryTreeNode(8); BinaryTreeNode nodeA3 = new BinaryTreeNode(9); BinaryTreeNode nodeA4 = new BinaryTreeNode(2); BinaryTreeNode nodeA5 = new BinaryTreeNode(5); nodeA1.rightChild = nodeA2; nodeA2.rightChild = nodeA3; nodeA3.rightChild = nodeA4; nodeA4.rightChild = nodeA5; Assert.AreEqual(SubTreeHelper.HasSubTree(nodeA1, null), false); } // 09.樹A和樹B都為空樹 [TestMethod] public void HasSubTreeTest9() { Assert.AreEqual(SubTreeHelper.HasSubTree(null, null), false); }
3.3 測試結果
（1）測試通過情況
（2）代碼覆蓋率
浙公網安備 33010602011771號