【Leetcode】二叉树基础题思路

🔥个人主页：Quitecoder

🔥专栏：Leetcode刷题

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 通过递归的方法来比较给定的两棵树 p 和 q 的节点。递归的基本思路是从两棵树的根节点开始比较，然后依次递归地比较它们的左子树和右子树。具体步骤如下：

1. 检查基本情况:
   • 如果两个节点 p 和 q 都是 nullptr，即都不存在，那么它们被视为相同，因此返回 true。
   • 如果其中一个节点是 nullptr 而另一个不是（使用或操作符 || 判断），那么两棵树在结构上不相同，因此返回 false

if(p==NULL&&q==NULL)return true;
if(p==NULL||q==NULL)return false;

1. 比较节点值:
   • 如果两个节点都存在，那么接着比较它们的值（p->val 与 q->val）。如果值不相同，树不相同，返回 false

if(p->val!=q->val)return false;

1. 递归比较子树:
   • 如果到目前为止两个节点相同（即它们存在且值相同），继续递归比较左子树 p->left 和 q->left，以及右子树 p->right 和 q->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 函数通过以下步骤递归地比较两个给定的树（或子树）root1 和 root2：

1. 检查基本情况:
   • 如果 root1 和 root2 都是空（NULL），说明它们是对称的（或者都是叶子节点），返回 true。
   • 如果其中一个为空而另一个不为空，说明在这一层上树不对称，返回 false

if(root1==NULL&&root2==NULL)return true;
if(root1==NULL||root2==NULL)return false;

1. 比较节点值:
   • 如果两个节点都非空，首先比较它们的值 (root1->val 和 root2->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->left 和 root->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，说明 subRoot 是 root 的子树。否则，继续遍历 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 时，我们要注意几个基本的边界条件：

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

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