前言
本节是根据上篇博客遗留下的问题进行讲解,大家可以看下这篇博客:
相同的树
这题就是前一章题目的变形，方法基本一致,这里不做过多介绍,大家可以看下上篇博客
递归
class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { if(p==nullptr&&q==nullptr) { return true; } if(p==nullptr||q==nullptr) { return false; } if(p->val!=q->val) { return false; } return isSameTree(p->left,q->left)&& isSameTree(p->right,q->right); } };
迭代
class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { queue<TreeNode*> que; que.push(p); que.push(q); while (!que.empty()) { TreeNode* tree1 = que.front(); que.pop(); TreeNode* tree2 = que.front(); que.pop(); if (!tree1 && !tree2) continue; if (!tree1 || !tree2 || tree1->val != tree2->val) return false; que.push(tree1->left); que.push(tree2->left); que.push(tree1->right); que.push(tree2->right); } return true; } };
另一颗树的子树
递归
class Solution { public: bool compare(TreeNode* root, TreeNode* subRoot) { //如果两个都为空 if(root==NULL&&subRoot==NULL){ return true; } //如果只有一个为空 if(root==NULL||subRoot==NULL){ return false; } //如果两个都不空，结点值也不同，那直接返回false if(root->val!=subRoot->val){ return false; } //如果现在结点值和子树结点值相同，再分别检查两个的左右孩子 return compare(root->left, subRoot->left) && compare(root->right, subRoot->right); } bool isSubtree(TreeNode* root, TreeNode* subRoot) { //如果要检查的子树为空，那么不用查了，肯定对的 if(subRoot == NULL) return true; //如果要检查的子树不空，但root是空的，那也不用查了，错的。 if(root == NULL) return false; //要么是它本身，要么是它左子树，要么是它的右子树 return compare(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot); } };
