【初阶数据结构篇】二叉树OJ题

熬夜学编程的小王

发布于 2024-11-20 20:35:07

2420

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！ 👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！ 🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++感兴趣的朋友，让我们一起进步！

1. 题目一（单值二叉树）

1.1 题目链接：

965. 单值二叉树 - 力扣（LeetCode）

1.2 题目描述

补充：

根节点与左右孩子的数值进行比较，如果相等依次递归左右子树，如果为空，或者两者对应的值相等，则返回true。若不相等则直接返回false。

1.3 示例代码：

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

2. 题目2（相同的树）

2.1 题目链接：

100. 相同的树 - 力扣（LeetCode）

2.2 题目描述

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

补充：

题目解析：

将两个数的根节点的值依次比较，依次递归两根节点的左子树，若根节点为空，直接返回true，或两根节点对应的值相等也返回true，对应的值不相等或一个根节点为空而另一个不为空直接返回false。

2.3 示例代码：

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;
        }
        if(isSameTree(p->left,q->left)&&isSameTree(p->right,q->right))
        return true;
        else{
            return false;
        }

    }
};

3. 题目3（对称二叉树）

3.1 题目链接：

100. 相同的树 - 力扣（LeetCode）

3.2 题目描述

给你一个二叉树的根节点 root ，检查它是否轴对称。

可以将该二叉树看成两个独立的二叉树，分别将“两个二叉树”的根节点传入，判断该是否为相同的二叉树。

3.3 示例代码：

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;
        }
        if(isSameTree(p->left,q->right)&&isSameTree(p->right,q->left))
        return true;
        else{
            return false;
        }
}

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return isSameTree(root->left,root->right);
    }
};

4. 题目4（另一棵树的子树）

4.1 题目链接：

572. 另一棵树的子树 - 力扣（LeetCode）

4.2 题目描述：

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

依次递归每个节点，将每个节点与SunRoot判断是否相等即可。

4.3 示例代码：

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;
        }
        if(isSameTree(p->left,q->left)&&isSameTree(p->right,q->right))
        return true;
        else{
            return false;
        }
}

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

5. 题目5（二叉树前序遍历）

5.1 题目链接：

144. 二叉树的前序遍历 - 力扣（LeetCode）

5.2 题目描述

给你二叉树的根节点 root ，返回它节点值的前序遍历。

给二叉树中节点总数开空间，根据根左右原则依次递归将数据尾插入数组中，直接返回这个数组即可。

5.3 示例代码：

typedef struct TreeNode TreeNode;
  int TreeSize(TreeNode* root)
 {
    if(root==NULL)
    {
        return 0;
    }
    return 1+TreeSize(root->left)+TreeSize(root->right);
 }

void _preorderTraversal(TreeNode* root,int* returnArr,int* pi)
{
    if(root==NULL)
    {
        return ;
    }
    returnArr[(*pi)++]=root->val;
    _preorderTraversal(root->left,returnArr,pi);
    _preorderTraversal(root->right,returnArr,pi);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize=TreeSize(root);
    int* returnArr=(int*)malloc(sizeof(int)*(*returnSize));
    int i=0;
    _preorderTraversal(root,returnArr,&i);
    return returnArr;
}