劍指Offer面試題：17.樹(shù)的子結(jié)構(gòu)
題目：輸入兩棵二叉樹(shù)A和B，判斷B是不是A的子結(jié)構(gòu)。例如下圖中的兩棵二叉樹(shù)，由于A中有一部分子樹(shù)的結(jié)構(gòu)和B是一樣的，因此B是A的子結(jié)構(gòu)。要查找樹(shù)A中是否存在和樹(shù)B結(jié)構(gòu)一樣的子樹(shù)，我們可以分成兩步：Step1.在樹(shù)A中找到和B的根結(jié)點(diǎn)的值一樣的結(jié)點(diǎn)R；Step2.判斷樹(shù)A中以R為根結(jié)點(diǎn)的子樹(shù)是不是包含和樹(shù)B一樣的結(jié)構(gòu)。很明顯，這是一個(gè)遞歸的過(guò)程。
一、題目：樹(shù)的子結(jié)構(gòu)
題目：輸入兩棵二叉樹(shù)A和B，判斷B是不是A的子結(jié)構(gòu)。例如下圖中的兩棵二叉樹(shù)，由于A中有一部分子樹(shù)的結(jié)構(gòu)和B是一樣的，因此B是A的子結(jié)構(gòu)。
該二叉樹(shù)的節(jié)點(diǎn)定義如下，這里使用C#語(yǔ)言描述：
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 核心步驟
要查找樹(shù)A中是否存在和樹(shù)B結(jié)構(gòu)一樣的子樹(shù)，我們可以分成兩步：
Step1.在樹(shù)A中找到和B的根結(jié)點(diǎn)的值一樣的結(jié)點(diǎn)R；
Step2.判斷樹(shù)A中以R為根結(jié)點(diǎn)的子樹(shù)是不是包含和樹(shù)B一樣的結(jié)構(gòu)。
很明顯，這是一個(gè)遞歸的過(guò)程。
2.2 代碼實(shí)現(xiàn)
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); } // 從根節(jié)點(diǎn)的左子樹(shù)開(kāi)始匹配Tree2 if (!result) { result = HasSubTree(root1.leftChild, root2); } // 如果左子樹(shù)沒(méi)有匹配成功則繼續(xù)在右子樹(shù)中繼續(xù)匹配Tree2 if (!result) { result = HasSubTree(root1.rightChild, root2); } } return result; } private static bool DoesTree1HasTree2(BinaryTreeNode root1, BinaryTreeNode root2) { if (root2 == null) { // 證明Tree2已經(jīng)遍歷結(jié)束，匹配成功 return true; } if (root1 == null) { // 證明Tree1已經(jīng)遍歷結(jié)束，匹配失敗 return false; } if (root1.Data != root2.Data) { return false; } // 遞歸驗(yàn)證左子樹(shù)和右子樹(shù)是否包含Tree2 return DoesTree1HasTree2(root1.leftChild, root2.leftChild) && DoesTree1HasTree2(root1.rightChild, root2.rightChild); }
三、單元測(cè)試
為了方便測(cè)試，這里封裝了一個(gè)設(shè)置指定根節(jié)點(diǎn)的左孩子和右孩子節(jié)點(diǎn)的方法：SetSubTreeNode
public void SetSubTreeNode(BinaryTreeNode root, BinaryTreeNode lChild, BinaryTreeNode rChild) { if (root == null) { return; } root.leftChild = lChild; root.rightChild = rChild; }
3.1 功能測(cè)試
// 01.樹(shù)中結(jié)點(diǎn)含有分叉，樹(shù)B是樹(shù)A的子結(jié)構(gòu) // 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.樹(shù)中結(jié)點(diǎn)含有分叉，樹(shù)B不是樹(shù)A的子結(jié)構(gòu) // 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 特殊輸入測(cè)試
// 03.樹(shù)中結(jié)點(diǎn)只有左子結(jié)點(diǎn)，樹(shù)B是樹(shù)A的子結(jié)構(gòu) // 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.樹(shù)中結(jié)點(diǎn)只有左子結(jié)點(diǎn)，樹(shù)B不是樹(shù)A的子結(jié)構(gòu) // 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.樹(shù)中結(jié)點(diǎn)只有右子結(jié)點(diǎn)，樹(shù)B是樹(shù)A的子結(jié)構(gòu) // 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.樹(shù)中結(jié)點(diǎn)只有右子結(jié)點(diǎn)，樹(shù)B不是樹(shù)A的子結(jié)構(gòu) // 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.樹(shù)A為空樹(shù) [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.樹(shù)B為空樹(shù) [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.樹(shù)A和樹(shù)B都為空樹(shù) [TestMethod] public void HasSubTreeTest9() { Assert.AreEqual(SubTreeHelper.HasSubTree(null, null), false); }
3.3 測(cè)試結(jié)果
（1）測(cè)試通過(guò)情況
（2）代碼覆蓋率
作者：周旭龍
出處：http://edisonchou.cnblogs.com
本文版權(quán)歸作者和博客園共有，歡迎轉(zhuǎn)載，但未經(jīng)作者同意必須保留此段聲明，且在文章頁(yè)面明顯位置給出原文鏈接。
浙公網(wǎng)安備 33010602011771號(hào)