剑指Offer面试题：17.树的子结构
一、题目：树的子结构
题目：输入两棵二叉树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）代码覆盖率
正文到此结束
