面试题18 树的子结构

题目描述

输入两颗二叉树A，B，判断B是不是A的子结构。
 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     bool DoesTree1hasTree2(TreeNode* pRoot1, TreeNode* pRoot2){
13         if (pRoot2 == NULL){
14             return true;
15         }
16         if (pRoot1 == NULL){
17             return false;
18         }
19         if (pRoot1->val != pRoot2->val){
20             return false;
21         }
22         return DoesTree1hasTree2(pRoot1->left, pRoot2->left) && DoesTree1hasTree2(pRoot1->right, pRoot2->right);
23     }
24     
25     bool HasSubtree(TreeNode* pRootA, TreeNode* pRootB)
26     {
27         if (pRootA == NULL || pRootB == NULL)
28             return false;
29         return DoesTree1hasTree2(pRootA, pRootB) ||
30             HasSubtree(pRootA->left, pRootB) ||
31             HasSubtree(pRootA->right, pRootB);
32     }
33 };