二叉树基础oj练习(对称二叉树、翻转二叉树、另一棵树的子树二叉树的构建及遍历)

简介: 二叉树基础oj练习(对称二叉树、翻转二叉树、另一棵树的子树二叉树的构建及遍历)

1.对称二叉树


题目详情



代码


bool _isSymmetric(struct TreeNode* root1,struct 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(struct TreeNode* root) {
  return  _isSymmetric(root->left,root->right);
}


思路

我们以“相同的树”那题思路拓展开,先创建子函数,传入左节点和右节点(要看是否对称,比较两边)

大的思路:先看根存在或相同否,根判断完后。开始左子树,递归调用函数。接着右子树也同理

聚焦于递归:函数的主体只是比较那个“根”的情况,但是每个子节点也是根,递归调用后,他们在他们的函数里就是根(所以来判断他们的相等或者为空情况),最后都是遇到空(到了整体树的叶),就停止了


2.翻转二叉树


题目详情



代码


struct TreeNode* invertTree(struct TreeNode* root) {
    if(root==NULL)
        return NULL;
    struct TreeNode* root1=invertTree(root->left);
    struct TreeNode* root2=invertTree(root->right);
    root->left=root2;//真翻转
    root->right=root1;//真翻转
   return root;
}


思路

很明确的一点是:我们要从根节点开始,递归地对树进行遍历

具体的实现方法:叶子节点先开始翻转(叶子下面都是NULL,交换后也没意义,叶子也是利用那两条“真翻转”语句来进行交换,交换后返回,去进行上一级节点)。

宏观上:如果当前遍历到的节点 root 的左右两棵子树都已经翻转,那么我们只需要交换两棵子树的位置,就完成了

通过递归的方式翻转左子树和右子树,并将左子树指向翻转后的右子树,右子树指向翻转后的左子树,最后返回当前节点


3.另一颗树的子树


题目详情



代码1


 bool isSameTree(struct TreeNode* q,struct TreeNode* p)
 {
     if(q==NULL&&p==NULL)
     {
        return true;
     }
     if(q==NULL||p==NULL)
     {
        return false;
     }
     if(q->val!=p->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)
    {
        if(isSameTree(root,subRoot))
        {
            return true;
        }
    }
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}


思路1

我们借用一下isSameTree的代码(来判断两个树是不是相同的),这题也是看root的子树有没有跟subroot有没有相同的。还是先处理根(因为每个左右子树进去后也是根)

要是val一相同,再看是不是一个树,要是就返回true了,不是就看左子树和右子树是不是


代码2


 bool isSameTree(struct TreeNode* q,struct TreeNode* p)
 {
     if(q==NULL&&p==NULL)
     {
        return true;
     }
     if(q==NULL||p==NULL)
     {
        return false;
     }
     if(q->val!=p->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;
    }
    return isSameTree(root,subRoot)||
     isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}


思路2


现在成了“三选一”了,也很好理解:三种情况有一种为真就返回true了

背后还是同一种思路不同的写法,背后的逻辑关系是一样的:看似少了一句root->val==subRoot->val,但是本身isSameTree就能进行跟是否相同的判断



4.二叉树的构建及遍历


题目详情



代码


#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef char BTDataType;
typedef struct BinaryTreeNode { //节点
    BTDataType data;//数据
    struct BinaryTreeNode* left;//左孩子
    struct BinaryTreeNode* right;//右孩子
} TreeNode;
TreeNode* createTree(char* arr, int* pi) {
    if (arr[*pi] == '#' || arr[*pi] == '\0') {
        (*pi)++;
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    assert(root);
    root->data = arr[*pi];
    (*pi)++;
    root->left = createTree(arr, pi);
    root->right = createTree(arr, pi);
    return root;
}
void PreOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    PreOrder(root->left);
    printf("%c ", root->data);
    PreOrder(root->right);
}
int main() {
    char arr[100] = { 0 };
    scanf("%s", arr);
    int i = 0;
    TreeNode* root = createTree(arr, &i);
    PreOrder(root);
    return 0;
}


今天就到这里啦!


目录
相关文章
|
算法 安全 PHP
密码学系列之二:密码学基本概念
密码学系列之二:密码学基本概念
1011 0
密码学系列之二:密码学基本概念
|
6月前
|
存储 Java API
Java Optional 完全指南:彻底告别 NullPointerException
Java 8 引入的 `Optional` 类旨在解决 `null` 带来的空指针异常问题,通过提供容器类显式处理可能为空的值,提升代码健壮性和可读性。本文从基础到进阶解析 `Optional` 的用法,涵盖创建、检查、获取值、处理值等核心功能,结合实际应用场景与最佳实践,助你彻底告别 `NullPointerException`,编写更优雅的 Java 代码。
306 0
|
11月前
|
前端开发 JavaScript
怎么在vite项目中全局导入一个scss文件
在Vite项目中全局导入SCSS文件的方法:通过配置`vite.config.js`中的`css.preprocessorOptions.scss.additionalData`属性,可以将SCSS变量或混合内容全局引入。此方法同样适用于LESS文件。详情参见Vite官方文档。
646 1
怎么在vite项目中全局导入一个scss文件
|
12月前
Vue3 中使用 Event Bus
【10月更文挑战第16天】Event Bus 是 Vue3 中一种简单而实用的通信方式,在一些简单的场景中可以发挥重要作用。但在实际应用中,要根据项目的具体需求和复杂度,选择合适的通信方式,以实现最佳的性能和可维护性。同时,要遵循最佳实践,合理使用 Event Bus,避免出现问题。
1194 60
|
存储 Linux 5G
Linux 基于 LVM 逻辑卷的磁盘管理【简明教程】
这篇文章介绍了LVM(逻辑卷管理)如何提供灵活的磁盘管理方式,允许动态调整逻辑卷的大小而不会丢失数据。
Linux 基于 LVM 逻辑卷的磁盘管理【简明教程】
|
12月前
|
安全 网络安全 数据安全/隐私保护
【Azure Developer】System.Net.WebException: The request was aborted: Could not create SSL/TLS secure channel.
System.Net.WebException: The request was aborted: Could not create SSL/TLS secure channel.
157 2
|
机器学习/深度学习 人工智能 前端开发
探索未来:2024年前端技术趋势解读
探索未来:2024年前端技术趋势解读
540 4
|
存储 弹性计算 网络协议
阿里云ECS内存型实例规格族特点、适用场景、指标数据参考
阿里云ECS提供了多样化的内存型实例规格族,专为需要高性能内存资源的应用场景设计。从最新的r8a系列到经过优化的re6p系列,旨在提供稳定、高效且安全的计算环境。这些实例不仅具备强大的计算性能与内存配比,还通过支持ESSD云盘和高效网络协议,显著提升了存储I/O能力和网络带宽,适用于大数据分析、高性能数据库、内存密集型应用等多种场景,为用户带来卓越的计算体验。本文将详细解析阿里云ECS中的多个内存型实例规格族,包括它们的核心特点、适用场景、实例规格及具体指标数据,为用户在云计算资源选型时提供参考。
|
机器人 Shell 开发者
`roslibpy`是一个Python库,它允许非ROS(Robot Operating System)环境(如Web浏览器、移动应用等)与ROS环境进行交互。通过使用`roslibpy`,开发者可以编写Python代码来远程控制ROS节点,发布和订阅话题,以及调用服务。
`roslibpy`是一个Python库,它允许非ROS(Robot Operating System)环境(如Web浏览器、移动应用等)与ROS环境进行交互。通过使用`roslibpy`,开发者可以编写Python代码来远程控制ROS节点,发布和订阅话题,以及调用服务。
|
敏捷开发 Kubernetes 持续交付
阿里云云效产品使用合集之如何将流水线部署到Windows
云效作为一款全面覆盖研发全生命周期管理的云端效能平台,致力于帮助企业实现高效协同、敏捷研发和持续交付。本合集收集整理了用户在使用云效过程中遇到的常见问题,问题涉及项目创建与管理、需求规划与迭代、代码托管与版本控制、自动化测试、持续集成与发布等方面。