题目:输入两棵二叉树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;
}
}
要查找树A中是否存在和树B结构一样的子树,我们可以分成两步:
Step1.在树A中找到和B的根结点的值一样的结点R;
Step2.判断树A中以R为根结点的子树是不是包含和树B一样的结构。
很明显,这是一个递归的过程。
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;
}
// 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);
}
// 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);
}
(1)测试通过情况
(2)代码覆盖率
作者:周旭龙
出处:http://edisonchou.cnblogs.com
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。