二叉树--OJ2
1.判断两棵树是否相同
bool sametree(TreeNode* root1,TreeNode* root2){if(root1==NULL&&root2==NULL)return 1;if(root1==NULL||root2==NULL)return 0;if(root1->val!=root2->val)return 0;return sametree(root1->left,root2->left)&&sametree(root1->right,root2->right)}
2.另一棵树的子树
class Solution {
public:TreeNode* PreOrder(TreeNode* root,int a) {if (root == NULL) {return NULL;}if(root->val==a){return root;}auto r1=PreOrder(root->left,a);if(r1)return r1;auto r2=PreOrder(root->right,a);return r2;}bool sametree(TreeNode* root1, TreeNode* root2) {if (root1 == NULL && root2 == NULL)return 1;if (root1 == NULL || root2 == NULL)return 0;if(root1->val!=root2->val)return 0;return sametree(root1->left, root2->left) &&sametree(root1->right, root2->right);}bool isSubtree(TreeNode* root, TreeNode* subRoot) {int a=subRoot->val;while(auto b=PreOrder(root, a)){if(sametree(b, subRoot)){return 1;}b->val=(!a);}return 0;}
};
法二
class Solution {
public:bool sametree(TreeNode* root1, TreeNode* root2) {if (root1 == NULL && root2 == NULL)return 1;if (root1 == NULL || root2 == NULL)return 0;if(root1->val!=root2->val)return 0;return sametree(root1->left, root2->left) &&sametree(root1->right, root2->right);}bool isSubtree(TreeNode* root, TreeNode* subRoot) {if(root==NULL)return 0;if(sametree(root, subRoot))return 1;return isSubtree(root->left, subRoot)||isSubtree(root->right, subRoot);}
};
对称二叉树
class Solution {
public:bool sametree(TreeNode* root1, TreeNode* root2) {if (root1 == NULL && root2 == NULL)return 1;if (root1 == NULL || root2 == NULL)return 0;if(root1->val!=root2->val)return 0;return sametree(root1->left, root2->left) &&sametree(root1->right, root2->right);}bool isSubtree(TreeNode* root, TreeNode* subRoot) {if(root==NULL)return 0;if(sametree(root, subRoot))return 1;return isSubtree(root->left, subRoot)||isSubtree(root->right, subRoot);}
};