坚持刷题|重建二叉树

article/2024/2/25 9:43:22

文章目录

  • 题目
  • 考察点
  • 代码实现
  • 实现总结
  • 扩展问题
    • 从前序和中序遍历中序列构建二叉树
      • 题目
      • 代码实现
      • 与后序实现的异同点
    • 前序和后序可不可以唯一确定一棵二叉树呢?

Hello,大家好,我是阿月。坚持刷题,老年痴呆追不上我,今天刷:重建二叉树

题目

106. 从中序与后序遍历序列构造二叉树
在这里插入图片描述

考察点

不仅考察了对数据结构和算法的理解,还考察了如何将理论知识转化为实际的代码实现,并且需要考虑算法的效率和优化:

  • 二叉树的遍历:需要理解中序遍历和后序遍历的概念,并知道它们的应用场景和特点。
  • 递归:在构造二叉树的过程中,需要使用递归算法来处理子树。
  • 数组操作:需要熟练地对数组进行索引和切片操作,以便在中序和后序遍历序列中定位根节点和子树的范围。
  • 二叉树的构造:理解如何根据中序遍历和后序遍历序列构造二叉树,包括根据根节点在中序遍历中的位置将树分割成左右子树,并且根据后序遍历序列确定左右子树的范围。
  • 时间复杂度分析:在实现算法时需要考虑其时间复杂度,尤其是递归算法的时间复杂度分析,以确保算法的效率。

代码实现

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}public class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {if (inorder == null || postorder == null || inorder.length != postorder.length) {return null;}return buildTreeHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);}private TreeNode buildTreeHelper(int[] inorder, int inStart, int inEnd,int[] postorder, int postStart, int postEnd) {if (inStart > inEnd || postStart > postEnd) {return null;}int rootValue = postorder[postEnd];TreeNode root = new TreeNode(rootValue);int rootIndex = 0;for (int i = inStart; i <= inEnd; i++) {if (inorder[i] == rootValue) {rootIndex = i;break;}}int leftTreeSize = rootIndex - inStart;root.left = buildTreeHelper(inorder, inStart, rootIndex - 1,postorder, postStart, postStart + leftTreeSize - 1);root.right = buildTreeHelper(inorder, rootIndex + 1, inEnd,postorder, postStart + leftTreeSize, postEnd - 1);return root;}public static void main(String[] args) {Solution solution = new Solution();int[] inorder = {9, 3, 15, 20, 7};int[] postorder = {9, 15, 7, 20, 3};TreeNode root = solution.buildTree(inorder, postorder);// 在这里可以添加遍历树的代码来验证结果}
}

实现总结

  • 首先通过后序遍历的最后一个节点找到根节点的值,然后根据中序遍历序列将其分割成左子树和右子树,接着根据后序遍历序列确定左子树和右子树的范围,最后递归构造左子树和右子树即可。
  • 时间复杂度
  • 递归
    • 递归函数返回值以及参数:
      • 返回值:重建好的二叉树。
      • 参数:中序遍历序列,中序的开始坐标,中序的结束坐标,后序遍历序列,后序的开始坐标,后序的结束坐标。
    • 终止条件:
      • 如果中序遍历或者后序遍历的开始坐标大于结束坐标(inStart > inEnd || postStart > postEnd),也就是数组大小为零,说明是空节点,直接返回。
    • 单层递归逻辑:
      • 通过后序遍历找到根节点的值。
      • 根据根节点的值将中序遍历分割为左子树和右子树。
      • 根绝中序遍历切割的左子树和右子树size对后序遍历进行左右子树范围切割。
  • 时间复杂度:O(n^2)。
    • 首先,在每个节点的递归调用中,需要在中序遍历序列中搜索根节点的位置。这个操作的时间复杂度是 O(n),因为在最坏的情况下,可能需要遍历整个中序遍历序列来找到根节点的位置。
    • 然后,对每个节点都会进行递归操作。在最坏情况下,每个节点都需要处理一次,因此总的时间复杂度是 O(n)。
    • 总体来说,这个算法的时间复杂度是 O(n^2)。

扩展问题

从前序和中序遍历中序列构建二叉树

题目

105. 从前序与中序遍历序列构造二叉树
在这里插入图片描述

代码实现

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}public class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder == null || inorder == null || preorder.length != inorder.length) {return null;}return buildTreeHelper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);}private TreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd,int[] inorder, int inStart, int inEnd) {if (preStart > preEnd || inStart > inEnd) {return null;}int rootValue = preorder[preStart];TreeNode root = new TreeNode(rootValue);int rootIndex = 0;for (int i = inStart; i <= inEnd; i++) {if (inorder[i] == rootValue) {rootIndex = i;break;}}int leftTreeSize = rootIndex - inStart;root.left = buildTreeHelper(preorder, preStart + 1, preStart + leftTreeSize,inorder, inStart, rootIndex - 1);root.right = buildTreeHelper(preorder, preStart + leftTreeSize + 1, preEnd,inorder, rootIndex + 1, inEnd);return root;}public static void main(String[] args) {Solution solution = new Solution();int[] preorder = {3, 9, 20, 15, 7};int[] inorder = {9, 3, 15, 20, 7};TreeNode root = solution.buildTree(preorder, inorder);// 在这里可以添加遍历树的代码来验证结果}
}

与后序实现的异同点

  • 异:
    • 根节点的确定:
      • 在前序遍历中,根节点总是序列的第一个元素。
      • 在后序遍历中,根节点总是序列的最后一个元素。
    • 子树的顺序划分:
      • 在前序遍历中,左子树的元素紧随着根节点之后,而右子树的元素在左子树元素之后,具有明显的顺序。
      • 在后序遍历中,右子树的元素位于根节点之前,而左子树的元素位于右子树之前,同样具有明显的顺序。
  • 同:
    • 从前序和中序遍历序列构建二叉树的递归过程和从后序和中序遍历序列构建二叉树的递归过程在本质上是相似的。

前序和后序可不可以唯一确定一棵二叉树呢?

  • 前序和后序不能唯一确定一棵二叉树。
  • 前序和中序可以唯一确定一棵二叉树,后序和中序可以唯一确定一棵二叉树,是因为他们都有中序遍历确定左右子树部分。
  • 前序和后序没有中序遍历无法确定左右部分,也就是无法分割,无法确定唯一的一棵二叉树。

http://www.ngui.cc/article/show-1899206.html

相关文章

AtCoder Beginner Contest 340 C - Divide and Divide【打表推公式】

原题链接&#xff1a;https://atcoder.jp/contests/abc340/tasks/abc340_c Time Limit: 2 sec / Memory Limit: 1024 MB Score: 300 points 问题陈述 黑板上写着一个整数 N。 高桥将重复下面的一系列操作&#xff0c;直到所有不小于2的整数都从黑板上移除&#xff1a; 选择…

浅析Linux追踪技术之ftrace:Event Tracing

文章目录 概述使用Event Tracing使用set_event接口使用enable接口 Event配置Event formatEvent Filtering过滤规则设置过滤器 Event TriggerTrigger语法 Trace marker相关参考 概述 Event Tracing&#xff08;事件追踪&#xff09;利用在内核代码中加入的各种Tracepoint&#…

C++ 堆排序

C 堆排序 堆排序是一种基于二叉堆数据结构的排序算法&#xff0c;其原理如下&#xff1a; 构建最大堆&#xff1a;将待排序的数组看作一个完全二叉树&#xff0c;并通过调整节点的位置构建一个最大堆。最大堆满足每个父节点的值都大于或等于其子节点的值。构建最大堆的过程可以…

猫头虎分享:Win11系统家庭版组策略编辑器怎么打开? Windows11家庭版没有gpedit.msc如何解决?

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …

智胜未来,新时代IT技术人风口攻略-第一版(弃稿)

文章目录 抛砖引玉 鸿蒙生态小科普焦虑之下 理想要落到实处校园鼎力 鸿蒙发展不可挡培训入场 机构急于吃红利企业布局 鸿蒙应用规划动智胜未来 技术人风口来临 鸿蒙已经成为行业的焦点&#xff0c;未来的发展潜力无限。作为一名程序员兼UP主&#xff0c;我非常荣幸地接受了邀请…

Android 10.0 锁屏壁纸 LockscreenWallpaper

前言 一、设置壁纸 通过系统设置进行锁屏壁纸和桌面壁纸的设置。 Setting 部分的代码&#xff1a; packages/apps/WallpaperPicker2/src/com/android/wallpaper/module/DefaultWallpaperPersister.java private int setStreamToWallpaperManagerCompat(InputStream inputStre…

算法-3-基本的数据结构

单双链表 1.单链表双链表如何反转 import java.util.ArrayList; import java.util.List;public class Code01_ReverseList {public static class Node {public int value;public Node next;public Node(int data) {value data;}}public static class DoubleNode {public int…

spring boot整合cache使用Ehcache 进行数据缓存

之前的文章 spring boot整合 cache 以redis服务 处理数据缓存 便捷开发 带着大家通过spring boot整合了 cache 缓存 那么 我们就来说说 其他服务的缓存 而spring boot默认的缓存方案就是 cache 用simple模式 spring boot的强大在于它的整合能力 它将其他缓存技术整合 统一了接…

KY141 最大连续子序列

最长连续子序列和&#xff0c;区间DP ti #include<bits/stdc.h>using namespace std;int n, a[10010]; int res1, res2, ans; int dp[10010];int main() {while(cin>>n && n){memset(dp, 0, sizeof dp);bool f 1;for(int i 0; i < n; i ){cin>&g…

【Tauri】(2):使用Tauri应用开发,使用开源的Chatgpt-web应用做前端,使用rust 的candle做后端,本地运行小模型桌面应用

视频演示地址 https://www.bilibili.com/video/BV17j421X7Zc/ 【Tauri】&#xff08;2&#xff09;&#xff1a;使用Tauri应用开发&#xff0c;使用开源的Chatgpt-web应用做前端&#xff0c;使用rust 的candle做后端&#xff0c;本地运行小模型桌面应用 1&#xff0c;做一个免…