0 引言
题目：输入两棵二叉树A和B，判断B是不是A的子结构。约定空树不是任意一个树的子结构。二叉树结点的定义如下：
struct BinaryTreeNode { int val; BinaryTreeNode* left; BinaryTreeNode* right; };
1 抽象问题具体化
举例1：
举例2：A是任意树，B为空树，返回true；
举例3：A是空树，若B不是空树，返回false，否则，返回true。
2 具体问题抽象化
语言描述算法，并尝试用伪代码表述语言，一步一步达到可以运行的地步
1）输入两棵树，A和B. 必须A和B同时不为空，才不返回false.
if(!(pRoot1 != NULL && pRoot2 != NULL)) return false;
2）首先遍历树A，采用前序递归的遍历方法，出循环表示遍历完毕仍然没有找到A中的子结构与B相同，返回false.
bool HasSubTree(TreeNode* pRoot1, TreeNode* pRoot2){ if(!(pRoot1 != NULL && pRoot2 != NULL)) return false; // 访问根结点，如果找到了，则返回true. DoseTree1HasTree2(pRoot1, pRoot2); if(以根结点为子树根结点没找到) HasSubTree(pRoot1->left, pRoot2); //访问左子树 if(以左子树结点为子树根节点没找到) HasSubTree(pRoot1->right, pRoot2); //访问右子树 return result; }
3）如果满足当前结点值与B的根结点值相等，进入第二个递归遍历。
bool DoesTree1HasTree2(TreeNode* pRoot1, TreeNode* pRoot2){ 判断是否存在空树，如果pRoot2为空，返回true；如果pRoot1为空，返回false. 判断两棵树的根结点是否相等,如果不相等，返回false； 递归判断两棵树的左右子结点是否相等，直到某棵树为空，返回判断结果。 }
3 demo
/* ** 递归判断以pRoot1和pRoot2为根结点的两棵树是否具有相同的结构 * 输入判断：如果pRoot2为空，则两棵树具有相同的结构 * 如果pRoot2不为空，pRoot1为空，则两棵树必不具有相同的结构 * 如果两棵树根节点的值不相等，则两棵树必不具有相同的结构 * 递归：判断两个根节点的左子树与右子树是否具有相同的结构，必须同时具有相同的结构才可以输出true */ bool DoesTree1HasTree2(TreeNode* pRoot1, TreeNode* pRoot2){ if(pRoot2 == NULL) return true; if(pRoot1 == NULL) return false; if(pRoot1->val != pRoot2->val) return false; return DoesTree1HasTree2(pRoot1->left, pRoot2->left) && DoesTree1HasTree2(pRoot1->right, pRoot2->right); } bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { bool result = false; // 定义记录查找结果的变量，由于要进行多轮查找，这个变量是不可或缺的，可以简化代码结构 if(pRoot1 != NULL && pRoot2 != NULL) {
// 以A根结点为子树结点，查找相同子树结构 if(pRoot1->val == pRoot2->val) result = DoesTree1HasTree2(pRoot1, pRoot2);
// 如果没找到，到左子树中去找 if(!result) result = HasSubtree(pRoot1->left, pRoot2);
// 如果还是没找到，到右子树中去找 if(!result) result = HasSubtree(pRoot1->right, pRoot2); }
// 返回查找的结果 return result; }
4 代码优化
思路1：想办法把递归结构改成迭代结构