算法学习记录十三（C++）--->10年微软面试题树的子结构

描述

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

分析

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

第一步：找到相同根节点 第二步：找到相同根节点后匹配左右子树是否值都匹配

代码 (复杂flag版本但是思路很清晰)

/* 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 flag = false; // 当两棵树都不为空的时候进行匹配 if(!pRoot1 == NULL && !pRoot2 == NULL){ if(pRoot1->val == pRoot2->val){ // 当根节点相同的时候进行判断是否包含 flag = tree2ContainerTree1(pRoot1,pRoot2); } // 如果上面根节点不同，那么flag是no 或者根节点相同而且对应的flag匹配失败，还是no if(!flag){ flag = HasSubtree(pRoot1->left,pRoot2); } // 如果左子树未匹配到，那么进行右子树匹配 if(!flag){ flag = HasSubtree(pRoot1->right,pRoot2); } } return flag; } // 判断是否被包含 bool tree2ContainerTree1(TreeNode *node1, TreeNode *node2){ // 当node2的树遍历完的时候就是被包含的 if(node2 == NULL){ return true; } // 当node1的树提前结束，node2没结束，肯定不包含 if(node1 == NULL){ return false; } // 当某个节点不同的时候 不包含 if(node1->val != node2->val){ return false; } // 如果根节点都对的上，那么继续用子节点进行匹配，左右都匹配到的时候才算被包含 return tree2ContainerTree1(node1->left,node2->left) && tree2ContainerTree1(node1->right,node2->right); } }; */

代码（精简版本）

class Solution { public: bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { if(pRoot1 == NULL || pRoot2 == NULL)return false; return tree2ContainerTree1(pRoot1,pRoot2) || HasSubtree(pRoot1->left,pRoot2) || HasSubtree(pRoot1->right,pRoot2); } // 判断是否被包含 bool tree2ContainerTree1(TreeNode *node1, TreeNode *node2){ if(node2 == NULL) return true; if(node1 == NULL) return false; if(node1->val == node2->val){ return tree2ContainerTree1(node1->left,node2->left) && tree2ContainerTree1(node1->right,node2->right); }else{ return false; } } };

1.真的|| 运算符，C的特性就是当某一个为真的时候就不会继续向下运行，因此不会有过多的运算 2.tree2ContainerTree1 该方法是当根节点一致的时候，左右子树是否一致，当node2为空的时候 就是被包含了，如果node1提前为空，而node2还不为空，肯定不包含了，递归向左右进行节点判断 3.HasSubtree 当根节点一致的时候，就去调用tree2ContainerTree1 进行包含判断，但是如果不等，递归HasSubtree 进行匹配，直到节点相同进行包含判断，否则的话就是不包含