题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
一 . 二叉树的概念
树形结构是一种典型的非线性结构，除了用于表示相邻关系外，还可以表示层次关系。每个结点最多有两棵子树。左子树和右子树是有顺序的，次序不能任意颠倒。即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。即为下图。。
C#定义二叉树：
代码语言：javascript复制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两个二叉树，判断B是否为A的子结构。
想法：该题使用递归法。步骤为：在树A中找到和B的根结点的值一样的结点；判断以该节点为中心的左右子树是否相同，相同即为子结构，不同继续递归，直到结束。
三 . 代码实现：
代码语言：javascript复制class Solution
{
public bool HasSubtree(TreeNode pRoot1, TreeNode pRoot2)
{
// write code here
if(pRoot1 == null || pRoot2 == null)
{
return false;
}
else
{
return Judge(pRoot1,pRoot2);
}
}
public static bool Judge(TreeNode pRoot1, TreeNode pRoot2)
{
//解释说是pRoot2如果全部遍历完且与pRoot1一一对应，则返回正确
//如果pRoot2还没遍历完，而pRoot1已经遍历结束，则错误。
if (pRoot2 == null)
{
//递归成功条件，什么意思呢，比如B仅有一个节点，且存在和A一样的节点，那肯定是是咯
return true;
}
if (pRoot1 == null)
{
//递归失败条件，如果你一直递归下去，A都结束了，还没找到，那肯定不是咯。
return false;
}
if (pRoot1.val == pRoot2.val)
{
//递归成功条件2，左右节点都一样
if (Judge(pRoot1.left,pRoot2.left) && Judge(pRoot1.right,pRoot2.right))
{
return true;
}
}
//递归
return Judge(pRoot1.left,pRoot2) || Judge(pRoot1.right,pRoot2);
}
}PS：该题考点依旧是代码的鲁棒性，所以要格外注意，其实貌似就这么一处吧if(pRoot1 == null || pRoot2 == null)。。
