首页 > 编程语言 >算法力扣刷题记录 五十【106.从中序与后序遍历序列构造二叉树】和【105.从前序与中序遍历序列构造二叉树】

算法力扣刷题记录 五十【106.从中序与后序遍历序列构造二叉树】和【105.从前序与中序遍历序列构造二叉树】

时间:2024-07-18 11:56:32浏览次数:19  
标签:遍历 TreeNode int right 二叉树 序列 left inorder postorder

前言

记录 三十八的四、二叉树构建通过层序遍历的数组实现。

层序遍历中,某个节点下标是i,那么左孩子的下标2i+1,右孩子的下标2i+2。这是统一的规律。

那么通过中序序列和后序序列如何构造二叉树?通过中序序列和前序序列如何构造二叉树?通过前序序列和后序序列如何构造二叉树?


一、【106.从中序与后序遍历序列构造二叉树】题目阅读

给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

示例 1:
在这里插入图片描述

输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出:[3,9,20,null,null,15,7]

示例 2:

输入:inorder = [-1], postorder = [-1]
输出:[-1]

提示:

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由 不同 的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历

二、【106.从中序与后序遍历序列构造二叉树】思路获取

参考思路链接

拿到题目分析:尝试看某个元素左右相邻的数值规律,没有成型的思路,所以先通过参考学习思路。

  1. 中序:左中右;后序:左右中。
  2. 确定后序的最后一位一定是中间节点(整个树的根节点)。
  3. 拿到中间节点,在中序中找中间节点的位置,该位置左边区间所有数值是它的左子树;该位置右边区间所有数值是它的右子树。以中间节点为界,分成左右两边区间
  4. 以左区间内容在后序中比较,确定后序数组中左右的分界;相应剩下的是右区间。
  5. 深入左区间,重复2-4步骤,可以建立左子树;深入右区间,重复2-4步骤,可以建立右子树。
  6. 核心
  • 后序数组确定中间节点;
  • 中序数组以中间节点为界,划分左右区间;
  • 以分出来的左右区间,确定后序左右子树的界限。再次重复。(这个重复就是递归逻辑)
    在这里插入图片描述

三、【106.从中序与后序遍历序列构造二叉树】代码实现

有了思路后,先尝试代码实现:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        //终止条件
        if(postorder.size() == 0) return nullptr;

        //终止条件,如果后序只有一个节点,是一个节点的树。
        TreeNode* root = new TreeNode(postorder[postorder.size()-1]);//创建根节点
        if(postorder.size() == 1) return root;//返回上一层,把这个创建的根节点返回去

        //在中序数组中分出左右两边子树,整个区间坚持左闭右闭。
        int index = 0;
        for(;index < inorder.size();index++){
            if(inorder[index] == postorder[postorder.size()-1]) break;
        }
        //左子树长度是index
        vector<int> lefttree_inorder;
        for(int i = 0;i < index;i++){
            lefttree_inorder.push_back(inorder[i]);
        }
        //右子树长度inorder.size()-index-1
        vector<int> righttree_inorder;
        for(int i = index+1,j = 0;i < inorder.size();i++){
            righttree_inorder.push_back(inorder[i]);
        }

        //从后序数组中找到左右区间的分界
        vector<int> lefttree_postorder;
        for(int i = 0;i < index;i++){//截取长度index
            lefttree_postorder.push_back(postorder[i]);
        }
        vector<int> righttree_postorder;
        for(int i = index;i < postorder.size()-1;i++){//从下标index开始,到最后一个元素之前
            righttree_postorder.push_back(postorder[i]);
        }

        //深入左子树和右子树
        TreeNode* leftroot = buildTree(lefttree_inorder,lefttree_postorder);
        TreeNode* rightroot = buildTree(righttree_inorder,righttree_postorder);
        root->left = leftroot;
        root->right = rightroot;
        return root;
    }
};

对比参考代码:

  • 在中序数组分左右时:

     // 左闭右开区间:[0, delimiterIndex)
    vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
    // [delimiterIndex + 1, end)
    vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
    
  • 在后序中分左右时:

    // postorder 舍弃末尾元素,因为这个元素就是中间节点,已经用过了
    postorder.resize(postorder.size() - 1);
    
    // 左闭右开,注意这里使用了左中序数组大小作为切割点:[0, leftInorder.size)
    vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
    // [leftInorder.size(), end)
    vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
    
  • 参考使用构造函数,遵循左闭右开区间规则;代码实现使用for循环填充元素,遵循左闭右闭区间规则

改进【使用下标分割】

【使用下标分割】思路:

  1. 上面每一次递归,分割数组都是建立4个新数组,开辟空间后,传递给下一层;
  2. 使用同一个数组,每一层传入下标值,这样不用新建数组。
  3. 不过8个下标要确认好

【使用下标分割】代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* build(vector<int>& inorder,vector<int>& postorder,int inorder_left,int inorder_right,int postorder_left,int postorder_right){
        //左闭右开规则
        //终止条件,对应后序数组为空
        if(postorder_left == postorder_right) return nullptr;
        //终止条件,后序只有一个节点,是一个节点的树。
        TreeNode* root = new TreeNode(postorder[postorder_right-1]);
        if(postorder_right - postorder_left == 1) return root;

        //找中间节点在中序数组的位置
        int index = inorder_left;
        for(;index < inorder_right;index++){
            if(inorder[index] == postorder[postorder_right-1]) break;
        }
        //中序数组左区间:[inorder_left,index)。右区间:[index+1,inorder_right)
        int leftinorderbegin = inorder_left;
        int leftinorderend = index;
        int rightinorderbegin = index+1;
        int rightinorderend = inorder_right;
        //长度:index-inorder_left
        //找后序数组的左右分界:[postorder_left,postorder_left+index-inorder_left)。右区间传参:[postorder_left+index-inorder_left,postorder_right-1)
        int leftpostbegin = postorder_left;
        int leftpostend = postorder_left+index-inorder_left;
        int rightpostbegin = postorder_left+index-inorder_left;
        int rightpostend = postorder_right-1;

        root->left = build(inorder,postorder,leftinorderbegin,leftinorderend,leftpostbegin,leftpostend);
        root->right = build(inorder,postorder,rightinorderbegin,rightinorderend,rightpostbegin,rightpostend);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return build(inorder,postorder,0,inorder.size(),0,postorder.size());
    }
};

四、【105.从前序与中序遍历序列构造二叉树】题目阅读

给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。

示例 1:
在这里插入图片描述

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列

五、【105.从前序与中序遍历序列构造二叉树】思路和代码实现

思路

和【106.通过中序和后序构建二叉树】基本一致,区别:前序的中在最前面

代码实现1【创建数组】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        //这个子树没有元素。说明空
        if(preorder.size() == 0) return nullptr;

        //子树只有一个元素
        TreeNode* root = new TreeNode( preorder[0]);
        if(preorder.size() == 1) return root;

        //子树有多个元素
        //拿着root的值去分割inorder
        int index = 0;  //index就是长度
        for(;index < inorder.size();index++){
            if(inorder[index] == preorder[0]) break;
        }
        //左闭右开
        vector<int> leftinorder(inorder.begin(),inorder.begin()+index);
        vector<int> rightinorder(inorder.begin()+index+1,inorder.end());

        //用左右区间分割前序数组
        vector<int> leftpreorder(preorder.begin()+1,preorder.begin()+1+index);
        vector<int> rightpreorder(preorder.begin()+1+index,preorder.end());

        root->left = buildTree(leftpreorder,leftinorder);
        root->right = buildTree(rightpreorder,rightinorder);
        return root;

    }
};

代码实现2【下标分割,不创建数组】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* build(vector<int>& preorder,vector<int>& inorder,int preorder_left,int preorder_right,int inorder_left,int inorder_right){
        //这个子树没有元素。说明空
        if(preorder_left == preorder_right) return nullptr;

        //子树只有一个元素
        TreeNode* root = new TreeNode(preorder[preorder_left]);
        if(preorder_right - preorder_left == 1) return root;

        //子树有多个元素
        //拿着root的值去分割inorder
        int index = inorder_left;
        for(;index < inorder_right;index++){
            if(inorder[index] == preorder[preorder_left]) break;
        }
        //左闭右开
        int leftinorderbegin = inorder_left;
        int leftinorderend = index;
        int rightinorderbegin = index+1;
        int rightinorderend = inorder_right;

        //用左右区间分割前序数组
        int leftpreorderbegin = preorder_left+1;
        int leftpreorderend = preorder_left+1+index-inorder_left;
        int rightpreorderbegin = leftpreorderend;
        int rightpreorderend = preorder_right;

        root->left = build(preorder,inorder,leftpreorderbegin,leftpreorderend,leftinorderbegin,leftinorderend);
        root->right = build(preorder,inorder,rightpreorderbegin,rightpreorderend,rightinorderbegin,rightinorderend);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder,inorder,0,preorder.size(),0,inorder.size());

    }
};

总结

构造二叉树
在这里插入图片描述

(欢迎指正,转载标明出处)

标签:遍历,TreeNode,int,right,二叉树,序列,left,inorder,postorder
From: https://blog.csdn.net/danaaaa/article/details/140495310

相关文章

  • [MRCTF2020]Ezpop(反序列化)
    打开题目即可得源码Welcometoindex.php<?php//flagisinflag.php//WTFISTHIS?//LearnFromhttps://ctf.ieki.xyz/library/php.html#%E5%8F%8D%E5%BA%8F%E5%88%97%E5%8C%96%E9%AD%94%E6%9C%AF%E6%96%B9%E6%B3%95//AndCrackIt!classModifier{protected$var......
  • 从前序与中序遍历序列构造二叉树-递归
    题目描述:个人题解:        只要我们在中序遍历中定位到根节点,那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的,因此我们就可以对应到前序遍历的结果中,对上述形式中的所有左右括号进行定位。这样的话,我们就......
  • wps office 2019 Pro Plus 集成序列号Vba安装版
    前言wpsoffice2019专业增强版含无云版是一款非常方便的办公软件,我们在日常的工作中总会碰到需要使用WPS的时候,它能为我们提供更好的文档编写帮助我们更好的去阅读PDF等多种格式的文档,使用起来非常的快捷方便。使用某银行专业增强版制作,包含vba和Pdf,集成序列号,去除密匙校验,去除......
  • Java二叉树经典例题
    目录一.相同的树二.翻转二叉树三.平衡二叉树四.对称二叉树五.根据前(后)和中序排序构建二叉树1.前序和中序构建2.后序和中序构建六.二叉树的层序遍历七.二叉树非递归遍历1.前序遍历2.中序遍历3.后序遍历八.总结前言:前面说过树是通过递归定义的。做二叉树的题,递......
  • 树与二叉树
    树与二叉树目录树与二叉树基本概念基本术语根双亲结点孩子节点节点的层次节点的度叶子树的高度有序树与无序树二叉树二叉树概念:二叉树基本特性满二叉树/完美二叉树:完全二叉树:平衡二叉树:退化二叉树:二叉树的链式存储树的遍历BST树基本概念插入节点删除节点遍历代码基本概念树是一......
  • Python对商店数据进行lstm和xgboost销售量时间序列建模预测分析|附代码数据
    全文下载链接:http://tecdat.cn/?p=17748最近我们被客户要求撰写关于销售量时间序列建模的研究报告,包括一些图形和统计输出。在本文中,在数据科学学习之旅中,我经常处理日常工作中的时间序列数据集,并据此做出预测我将通过以下步骤:探索性数据分析(EDA)问题定义(我们要解决什么)变量......
  • Python文件与数据处理:掌握I/O操作与序列化的艺术
    在Python编程的世界里,文件操作和数据序列化犹如画家手中的画笔和调色板,是构建强大应用程序不可或缺的工具。本文将深入探讨open()函数的巧妙使用、JSON和pickle模块的序列化魔法,以及os模块在文件系统操作中的关键角色。让我们一同揭开Python文件与数据处理的神秘面纱,掌握I/O操......
  • Netcode for Entities如何添加自定义序列化,让GhostField支持任意类型?以int3为例(1.2.3
    一句话省流:很麻烦也很抽象,能用内置支持的类型就尽量用。首先看文档。官方文档里一开头就列出了所有内置的支持的类型:GhostTypeTemplates其中Entity类型需要特别注意一下:在同步这个类型的时候,如果是刚刚Instantiate的Ghost(也就是GhostId尚未生效,上一篇文章里说过这个问题),那么客......
  • 查找时间序列数据中异常值的终极指南(第 1 部分)
    时间序列分析中异常值检测的有效统计方法和工具   异常值:这些令人困扰的数据点可能会扭曲统计模型、扭曲预测并破坏决策过程。    雲闪世界专门介绍时间序列数据中异常值的识别和管理的四部分系列文章的开篇,我们将探索视觉和统计方法来有效识别时间序列数据中的......
  • 题解:P10722 [GESP202406 六级] 二叉树
    题意一颗\(n\)节点的二叉树,每个节点非黑即白,给你\(Q\)次操作,每次给你一个\(u\),把\(u\)的子树内所有节点颜色反转,问最终每个节点的颜色。分析看到数据范围,首先把操作离线。容易发现如果一个节点重复操作奇数次,等效于操作一次,如果重复操作偶数次,等效于没操作。所以我们可......