初阶数据结构二叉树练习系列（1）
这个系列的文章将带大家一起刷题，并且总结思路
温馨提示：本篇文章里的练习题仅适合刚学完二叉树的小白使用
相同的树
思路
情况分析：第一种情况：两棵树都为空 → 返回true
第二种情况：一棵树为空，另一棵树不为空→ 返回false
第三种情况： 两棵树都不为空 → 判断每个节点的数值是否相同
源代码
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
if(q == NULL && p == NULL)
return true;
if(q == NULL || p == NULL)
return false;
if(p->val != q->val)
return false;
return isSameTree(q->left, p->left) && isSameTree(q->right, p->right);
}
变式题
思路上与第一题的一模一样，但不同的是这次需要遍历树的左右叶子，并且判断是否处在相反的位置
思路
情况分析：第一种情况：两棵树都为空 → 返回true
第二种情况：一棵树为空，另一棵树不为空→ 返回false
第三种情况： 两棵树都不为空 → 判断每个节点的数值是否相同
源代码
bool _isSymmetric(struct TreeNode* p, struct TreeNode* q)
{
if(q == NULL && p == NULL)
return true;
if(q == NULL || p == NULL)
return false;
if( q->val != p->val)
return false;
return _isSymmetric(q->left, p->right) && _isSymmetric(q->right, p->left);
}
bool isSymmetric(struct TreeNode* root) {
return _isSymmetric(root->left, root->right);
}
另一棵树的子树
思路
另一棵树的子树
第二种情况： root为空时， 则没有子树可与还在等待比较的树进行比较，因此返回false
第三种情况：root不为空，则先比较根节点的值是否相等，比较完根的节点后，再比较叶子的节点的数值是否相等
源代码
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
if(q == NULL && p == NULL)
return true;
if(q == NULL || p == NULL)
return false;
if(p->val != q->val)
return false;
return isSameTree(q->left, p->left) && isSameTree(q->right, p->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
if(root == NULL)
return false;
if(root->val == subRoot->val && isSameTree(root, subRoot))
return true;
return isSubtree(root->left, subRoot) || isSubtree(root->right,subRoot);
}
刷题总结
从本篇文章中的三道习题以及我自己的刷题中发现，类似于这种类型的题不管考察的是否为二叉树也好还是链表也好，我们都需要考虑它是否为空以及为空时是否可取
好的，本篇文章就先带大家刷到这里，还请各位观众老爷赏个三连，谢谢啦
