【Leetcode】二叉树基础题思路-LMLPHP

🔥个人主页Quitecoder

🔥专栏Leetcode刷题

【Leetcode】二叉树基础题思路-LMLPHP

1.单值二叉树

单值二叉树是所有节点的值都相同的二叉树。实现这个检查的思路是通过递归方式遍历整棵树,并验证每个节点是否满足单值二叉树的条件

具体来说,递归函数 isUnivalTree 的工作流程如下:

  1. 基本情况:
    • 如果当前节点 (root) 为空 (NULL),那么根据单值树的定义,它是单值的,因此返回 true
if(root==NULL)
{
   return true;
}
  1. 检查左子树:
    • 如果存在左子节点 (root->left),则进行两个检查:
      • 首先检查当前节点的值 (root->val) 是否与左子节点的值 (root->left->val) 相同。如果不相同,则整个树不可能是单值的,返回 false
      • 如果当前节点的值与左子节点的值相同,则递归调用 isUnivalTree(root->left) 来检查左子树是否为单值。如果左子树不是单值的,同样返回 false
if (root->left)
{
    if (root->val != root->left->val || !isUnivalTree(root->left))
        return false;
}
  1. 检查右子树:
    • 如果存在右子节点 (root->right),则进行类似的检查:
      • 检查当前节点的值 (root->val) 是否与右子节点的值 (root->right->val) 相同。如果不相同,返回 false
      • 如果当前节点的值与右子节点相同,则递归调用 isUnivalTree(root->right) 来检查右子树是否为单值。如果右子树不是单值的,同样返回 false
if (root->right)
{
    if (root->val != root->right->val || !isUnivalTree(root->right))
        return false;
}
  1. 返回结果:
    • 如果当前节点的值与它的子节点(如果有)都相同,并且子树也都是单值的,则返回 true,表示到目前为止,当前节点所在的子树是单值的。

总代码如下:

class Solution {
public:
    bool isUnivalTree(TreeNode* root) {
        if(root==NULL)
        {
            return true;
        }
        if(root->left)
        {
            if(root->val!=root->left->val||!isUnivalTree(root->left))
            return false;
        }
        if(root->right)
        {
            if(root->val!=root->right->val||!isUnivalTree(root->right))
            return false;
        }
        return  true;
    }
};

通过以上的递归过程,我们可以从根节点开始检查整棵树。只有当所有的节点与它们的子节点(如果有)都具有相同的值,并且所有的子树都是单值的时候,这棵树才是单值的。这种方法有效地使用了分治策略,将大问题分解成多个小问题,递归地解决每一个小问题

2.相同的树

这段代码实现的是一个用于检查两棵二叉树是否相同的函数 isSameTree。相同指的是两棵树具有相同的结构,且对应位置上的节点具有相同的值

函数 isSameTree 通过递归的方法来比较给定的两棵树 pq 的节点。递归的基本思路是从两棵树的根节点开始比较,然后依次递归地比较它们的左子树和右子树。具体步骤如下:

  1. 检查基本情况:
    • 如果两个节点 pq 都是 nullptr,即都不存在,那么它们被视为相同,因此返回 true
    • 如果其中一个节点是 nullptr 而另一个不是(使用或操作符 || 判断),那么两棵树在结构上不相同,因此返回 false
if(p==NULL&&q==NULL)return true;
if(p==NULL||q==NULL)return false;
  1. 比较节点值:
    • 如果两个节点都存在,那么接着比较它们的值(p->valq->val)。如果值不相同,树不相同,返回 false
if(p->val!=q->val)return false;
  1. 递归比较子树:
    • 如果到目前为止两个节点相同(即它们存在且值相同),继续递归比较左子树 p->leftq->left,以及右子树 p->rightq->right
    • 使用逻辑与操作符 && 来确保两个递归调用的结果都为 true。这意味着两个左子树和两个右子树都必须分别相同,整个树才相同
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);

如果所有对应的节点都满足结构相同且值相同的条件,递归过程最终会在所有叶子节点处结束。在这种情况下,函数返回 true,表明两棵树确实相同。如果任何节点不相同,函数会在那一点上返回 false

代码如下:

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p==NULL&&q==NULL)return true;
        if(p==NULL||q==NULL)return false;
        if(p->val!=q->val)return false;
        return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
    }
};

3.对称二叉树

这道题与上一道题思路十分类似

这道题isSymmetric 函数是这个功能的入口点,它提供了一个参数,而需要进行比较两个子树,我们需要提供两个参数,我们在这里自己构建一个子函数

 bool _isSymmetric(TreeNode*root1,TreeNode*root2)

_isSymmetric 函数通过以下步骤递归地比较两个给定的树(或子树)root1root2

  1. 检查基本情况:
    • 如果 root1root2 都是空(NULL),说明它们是对称的(或者都是叶子节点),返回 true
    • 如果其中一个为空而另一个不为空,说明在这一层上树不对称,返回 false
if(root1==NULL&&root2==NULL)return true;
if(root1==NULL||root2==NULL)return false;
  1. 比较节点值:
    • 如果两个节点都非空,首先比较它们的值 (root1->valroot2->val)。如果节点值不相同,树不对称,返回 false
if(root1->val!=root2->val) return false;
  1. 递归比较镜像子树:
    • 递归比较 root1 的左子树与 root2 的右子树,以及 root1 的右子树与 root2 的左子树。这两对子树必须分别是镜像对称的,整个树才是对称的。
    • 使用 && 运算符确保上述两个递归调用必须都为 true 才返回 true
return _isSymmetric(root1->left,root2->right)&&_isSymmetric(root1->right,root2->left);

isSymmetric 函数在被调用时,以给定树的根节点 root 的两个子节点 root->leftroot->right 作为参数来调用 _isSymmetric这对于开始对称性检查是合适的,因为对于树的根节点,我们要验证的是它的两个子节点是不是彼此的镜像

总代码如下:

class Solution {
public:
    bool _isSymmetric(TreeNode*root1,TreeNode*root2)
    {
        if(root1==NULL&&root2==NULL)return true;
        if(root1==NULL||root2==NULL)return false;
        if(root1->val!=root2->val) return false; 
        return _isSymmetric(root1->left,root2->right)&&_isSymmetric(root1->right,root2->left);
    }
    bool isSymmetric(TreeNode* root) {
            
         return _isSymmetric(root->left,root->right);
    }
};

4.另一棵树的子树

为了判断一棵树 subRoot 是否是另一棵树 root 的子树,我们需要遍历 root 并找到一个节点,该节点与 subRoot 的树根具有相同的值。一旦找到这样的节点,我们就需要检查从这个节点开始的子树是否与 subRoot 完全相同。上面 isSameTree 函数可以用来完成这个检查,因为它能够确定两棵树是否相同

实现 isSubtree 函数的步骤:

  1. 遍历 root 树。我们可以使用递归方式进行前序遍历(根节点 -> 左子树 -> 右子树)

  2. 在每个节点,使用 isSameTree 函数来检查以当前 root 中的节点为根的子树是否与 subRoot 树相同

  3. 如果 isSameTree 返回 true,说明 subRootroot 的子树。否则,继续遍历 root 的左右子节点

isSubtree 完整实现:

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p==NULL && q==NULL) return true;
        if(p==NULL || q==NULL) return false;
        if(p->val != q->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }

    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (subRoot == NULL) return true;
        if (root == NULL) return false;
        if (isSameTree(root, subRoot)) return true;
        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }
};

在实现 isSubtree 时,我们要注意几个基本的边界条件:

  • 如果 rootsubRoot 都为空,那么 subRootroot 的子树。
  • 如果 root 为空而 subRoot 不为空,那么 subRoot 不可能是 root 的子树。
  • 如果 rootsubRoot 的根节点值相同,我们需要使用 isSameTree 函数来检查它们是否结构和值完全相同。
  • 如果在当前节点没有找到与 subRoot 相同的子树,那么应该在 root 的左子树和右子树中继续寻找可能的匹配

本节内容到此结束!感谢阅读!

05-05 21:46