初阶数据结构二叉树练习系列（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);

}

刷题总结

从本篇文章中的三道习题以及我自己的刷题中发现，类似于这种类型的题不管考察的是否为二叉树也好还是链表也好，我们都需要考虑它是否为空以及为空时是否可取

好的，本篇文章就先带大家刷到这里，还请各位观众老爷赏个三连，谢谢啦