题目

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

考察点

• 树、指针、递归

解题思路

二叉树的遍历常用递归实现。先从A的根节点开始判断，若相同再去判断A的左右子树节点。

完整代码

/*17-树的子结构*/
#include<iostream>
using namespace std;
//树的创建
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};
class Solution {
public:bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2){bool  result = false;if (pRoot1 == NULL || pRoot2 == NULL)return false;if (pRoot1->val == pRoot2->val)//判断A的根是不是B的根，是就进行节点值递归判断result = isequal(pRoot1, pRoot2);if (!result)//上面不是，就判断左节点result = HasSubtree(pRoot1->left, pRoot2);if(!result)//左节点还是，就判断右节点result = HasSubtree(pRoot1->right, pRoot2);return result;}//递归实现，节点比较bool isequal(TreeNode* pRoot1, TreeNode* pRoot2){if (pRoot2 == NULL) return true;//pRoot2为空表明B树已经走完if (pRoot1 == NULL) return false;//if (pRoot1->val == pRoot2->val)return isequal(pRoot1->left, pRoot2->left) && isequal(pRoot1->right, pRoot2->right);elsereturn false;}
};
int main()
{TreeNode* A1 = new TreeNode(1); TreeNode* A2 = new TreeNode(2); TreeNode* A3 = new TreeNode(3);TreeNode* A4= new TreeNode(4); TreeNode* A5 = new TreeNode(5); A1->left = A2; A1->right = A3; A2->left = A4; A2->right = A5;TreeNode* B1 = new TreeNode(2); TreeNode* B2 = new TreeNode(3); TreeNode* B3 = new TreeNode(4);B1->left = B2; B1->right = B3;Solution s;cout << s.HasSubtree(A1, B2) << endl;return 0;
}