[程序员面试题精选100题]50.树的子结构

题目

输入两棵二叉树A和B，判断树B是不是A的子结构。

例如，下图中的两棵树A和B，，由于A中有一部分子树的结构和B是一样的，因此B就是A的子结构。

思路

这是2010年微软校园招聘时的一道题目。二叉树一直是微软面试题中经常出现的数据结构。对微软有兴趣的读者一定要重点关注二叉树。

回到这个题目的本身。要查找树A中是否存在和树B结构一样的子树，我们可以分为两步： （1）树A中找到和B的根结点的值一样的结点N （2）再判断树A中以N为根结点的子树是不是包括和树B一样的结构。

第一步在树A中查找与根结点的值一样的结点。这实际上就是树的遍历。对二叉树这种数据结构熟悉的读者自然知道我们可以用递归的方法去遍历，也可以用循环的方法去遍历。由于递归的代码实现比较简洁，面试时如果没有特别要求，我们通常都会采用递归的方式。

// 在root1中寻找与root2根节点值相同的节点bool FindSubTree(TreeNode* root1,TreeNode* root2){if(root2 == nullptr){return true;}//ifif(root1 == nullptr){return false;}//ifbool result = false;// 找到一个节点与root2根节点相同if(root1->val == root2->val){result = IsSubTree(root1,root2);}(!result){return FindSubTree(root1->left,root2) || FindSubTree(root1->right,root2);}//ifreturn result;}

在上述代码中，我们递归调用FindSubTree遍历二叉树A。如果发现某一结点的值和树B的头结点的值相同，则调用IsSubTree，做第二步判断。

在面试的时候，我们一定要注意边界条件的检查，即检查空指针。当树A或树B为空的时候，定义相应的输出。如果没有检查并做相应的处理，程序非常容易崩溃，这是面试时非常忌讳的事情。

接下来考虑第二步，判断以树A中以N为根结点的子树是不是和树B具有相同的结构。同样，我们也可以用递归的思路来考虑：如果结点N的值和树B的根结点不相同，则以N为根结点的子树和树B肯定不具有相同的结点返回false；如果他们的值相同，则递归地判断他们的各自的左右结点的值是不是相同。递归的终止条件是我们到达了树A或者树B的叶结点。

bool IsSubTree(TreeNode* root1,TreeNode* root2){if(root2 == nullptr){return true;}//ifif(root1 == nullptr){return false;}//ifif(root1->val != root2->val){return false;}IsSubTree(root1->left,root2->left) && IsSubTree(root1->right,root2->right);}

完整代码

/*————————————* 日期：2015-03-26* 作者：SJF0115* 题目: 50.树的子结构* 来源：程序员面试题精选100题—————————————*/;struct TreeNode{int val;TreeNode *left;TreeNode *right;TreeNode(int x):val(x),left(nullptr),right(nullptr){}};// 判断以root1为根节点的子树中是否和root2一样bool IsSubTree(TreeNode* root1,TreeNode* root2){if(root2 == nullptr){return true;}//ifif(root1 == nullptr){return false;}//ifif(root1->val != root2->val){return false;}IsSubTree(root1->left,root2->left) && IsSubTree(root1->right,root2->right);}// 在root1中寻找与root2根节点值相同的节点并判断以此为根节点的子树中是否包含root2bool FindSubTree(TreeNode* root1,TreeNode* root2){if(root2 == nullptr){return true;}//ifif(root1 == nullptr){return false;}//ifbool result = false;// 找到一个节点与root2根节点相同if(root1->val == root2->val){result = IsSubTree(root1,root2);}(!result){return FindSubTree(root1->left,root2) || FindSubTree(root1->right,root2);}//ifreturn result;}// 创建二叉树void CreateTree(TreeNode* &root){int val;cin>>val;if(val == -1){root = nullptr;return;}//ifroot = new TreeNode(val);// 左子树CreateTree(root->left);// 右子树CreateTree(root->right);}// 2.1 递归先序遍历void PreOrder(TreeNode* root,vector<int> &result){if(root == nullptr){return;}//ifresult.push_back(root->val);// 左子树PreOrder(root->left,result);// 右子树PreOrder(root->right,result);}// 输出结果void Print(vector<int> result){int size = result.size();for(int i = 0;i < size;++i){cout<<result[i]<<” “;}//forcout<<endl;}int main(){freopen(“C:\\Users\\Administrator\\Desktop\\c++.txt”, “r”, stdin);TreeNode *root1,*root2;vector<int> result;CreateTree(root1);PreOrder(root1,result);Print(result);result.clear();CreateTree(root2);PreOrder(root2,result);Print(result);result.clear();cout<<FindSubTree(root1,root2);return 0;}

你在会议中吵架时，尼泊尔的背包客一起端起酒杯坐在火堆旁。