【C++&数据结构】二叉树(结合C++)的经典oj例题 [ 盘点&全面解析 ](24)

本文涉及的产品
云解析DNS,个人版 1个月
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
简介: 【C++&数据结构】二叉树(结合C++)的经典oj例题 [ 盘点&全面解析 ](24)

一.二叉树创建字符串

1)题目介绍&oj链接

2)题目逐过程分析&完整代码

  • 主要思路是通过 前序遍历 (根->左子树->右子树)方式遍历二叉树
  • 我们可以利用 容器string += 追加字符【( 】【 )】
  • 于是我们得到下面所示基本代码

  • 注意点,题目的要求:转换后的结果如果右子树为空,则可以省略如果左子树为空,右子树不为空,则不省略 ,如下图所示:
  • 所以我们要在基础代码的基础上根据情况分类加上限定条件
  • 可以利用上 【||】自左向右进行判断 的性质
  • 分为以下三种情况(情况1&2可以合并成一种)
    1. 左子树为空,走【||】判断,右子树不为空——>打印左子树空括号
    2. 左子树不为空,直接进——>打印左子树括号+节点
    3.右子树不为空,直接进——>打印右子树括号+节点
  • (PS:由于加上了条件限制:左右均为空时,递归函数直接返回,不会打印空括号)
  • 最终代码如下图所示

二.给定一个二叉树, 找到该树中两个指定节点的最近公共祖先

1)题目介绍&oj链接

2)题目逐过程分析

  • 公共祖先的特征:一个节点在我的左子树,一个节点在我的右子树,则我就是公共祖先
  • 因此我们需要利用到【查找】功能(前序遍历:根—>左子树—>右子树)
  • 接下来我们进一步进行程序设计:
  • 首先明确传入的参数,1.树的根节点 2.节点1 3.节点2
  • 先得到一种情况:根节点为节点1/节点2,直接返回公共祖先
  • 之后需要对节点1和节点2是在左子树还是右子树进行 初步判断 ;设置四个参数,分别为节点在左还是在右的返回值;利用下图所示简单逻辑判断,快速得到返回值
  • 开始进行递归判断;两个节点,同时在左时,则继续往左走;同时在右时,继续往右走;直到一左一右,递归结束;

3)题目完整代码

4)方法2:引入栈存储【查找路径】,暴力求解

  • 将根元素入栈
  • 根据前序遍历向下探测查找元素,并分别入栈
  • 如果没找到元素(root为空时)return false,则跳出递归,将元素出栈(pop)
  • 经过FindPath这一过程以后,stack path中存储的是该节点TreeNode的路径
  • 最后分别对两个栈中存储的路径大小进行比较,大的路径挨个出栈,直到大小相同
  • 同时出栈,最后返回公共祖先

5)方法2的完整代码

三.二叉树搜索树转换成排序双向链表

1)题目介绍&oj链接

2)题目逐过程分析

  • 解题关键性质:二叉搜索树 中序遍历(左子树->根->右子树) 时,返回节点的顺序是 从小到大
  • 解题思路分析:
  • 核心:如果我们能够通过 中序遍历 该二叉搜索树,并且将返回的节点按顺序存入vector中,最后再将相邻元素两两连接,则也可以实现双向链表
  • 但是题目中要求如下所示:
  • 于是我们 只能 调节结点指针 角度出发
  • 结合上面的【核心】,我们知道要调节结点指针的指向——也就是 在中序遍历的过程中,让节点的左指针指向它的 前一个节点,右指针指向它的 下一个节点
  • 但是我们最多只能通过 前后指针法 ——> 来让节点的左指针指向它的前一个节点(上图中6—>4),至于让右指针指向它的后一个节点则做不到(上图中6—>8);
  • 但是我们可以 让前一组的右指针指向节点(4—>6)
  • 最后就是要找到 中序遍历 中的第一个节点head,不停地找左子树直到其为空即可

3)题目完整代码

四.根据一棵树的前序遍历与中序遍历构造二叉树

1)题目介绍&oj链接

2)题目逐过程分析

  • 这道题解题关键步骤在于: 利用 前序遍历 确定根,利用 中序遍历 分割左右区间

  • 根据以上核心思路:
  1. 我们需要一个 整型prei 在前序遍历中确定根—— prei记得要初始化成0
  2. 我们需要一个 节点rooti 在中序遍历中分割区间;
  • 程序设计板块:
    1. (第一次进入函数时)创建与前序遍历对应的根节点

    2. 利用while循环,在中序遍历中找到与 preorder[i] 对应的 节点rooti

    3. 前序遍历中确定下一个根

    4. 根据第2步找到的rooti, 划分左右区间 ,在左子树与右子树中进行递归操作

3)题目完整代码

4)对比同类型题目:“根据一棵树的中序遍历与后序遍历构造二叉树”

五.不使用递归,利用【迭代法】实现“前序遍历”

1)题目介绍&oj链接

2)题目逐过程分析

  • 核心思路:由于题目要求采用迭代法,所以我们要引入 【栈】
  • 概述:入手点应该放在 当前节点cur的变化(1) cur一直找左子树入栈 (2) cur找到空时,会开始出栈顶元素并压入vector中 (3) cur重新指向被出的栈顶元素的右子树根节点(重复上述过程直到cur为空且栈为空)
  • 程序设计板块:
    1. 设置一个栈,设置一个待返回的数组vector,设置一个指针cur指向当前节点

    2. 利用一个while循环,不停地取左树节点,并且 将节点压入栈中

    3. 取完左路节点时(当前所在节点为空时),将栈中的元素出栈的同时把节点的值push进要返回的数组vector中,随后访问其右路 (当前节点指向其右路节点)

4. 迭代法核心:用一个 while循环 嵌套 (跳出循环的条件:当前节点为空,且栈为空

  • (访问右路的过程,即是重复过程1的子问题如下图所示)

3)题目完整代码


相关文章
|
5天前
【数据结构OJ题】环形链表
力扣题目——环形链表
14 3
【数据结构OJ题】环形链表
|
4天前
|
存储 索引
【数据结构OJ题】设计循环队列
力扣题目——设计循环队列
14 1
【数据结构OJ题】设计循环队列
|
4天前
【数据结构OJ题】有效的括号
力扣题目——有效的括号
12 1
【数据结构OJ题】有效的括号
|
5天前
【数据结构OJ题】复制带随机指针的链表
力扣题目——复制带随机指针的链表
12 1
【数据结构OJ题】复制带随机指针的链表
|
5天前
【数据结构OJ题】环形链表II
力扣题目——环形链表II
10 1
【数据结构OJ题】环形链表II
|
5天前
【数据结构OJ题】相交链表
力扣题目——相交链表
14 1
【数据结构OJ题】相交链表
|
13天前
【数据结构OJ题】合并两个有序链表
力扣题目——合并两个有序链表
27 8
【数据结构OJ题】合并两个有序链表
|
15天前
【数据结构OJ题】移除链表元素
力扣题目——移除链表元素
17 2
【数据结构OJ题】移除链表元素
|
15天前
【数据结构OJ题】链表中倒数第k个结点
牛客题目——链表中倒数第k个结点
14 1
【数据结构OJ题】链表中倒数第k个结点
|
16天前
|
存储
【数据结构OJ题】轮转数组
力扣题目——轮转数组
17 2
【数据结构OJ题】轮转数组

推荐镜像

更多