二叉树刷题笔记(1)——LeetCode105_游离态GLZ不可能是金融技术宅的博客-程序员宝宝

技术标签: 算法  二叉树  LeetCode刷题笔记  leetcode  

最近刷题的时候发现很多搜索啊、动态规划啊,本质上都可以用树来理解,其中递归的思想在做题的时候也让人受益良多。本着复习一下树结构和精进递归思想的目的,最近刷了几题二叉树的题。

105. 从前序与中序遍历序列构造二叉树

这题保研前练习机试的时候就做过,是一个很能体现二叉树题目套路的题了。
二叉树的套路大体上记住两点:
(1)递归处理一切问题
(2)99%的题目本质上都是前/中/后序遍历,抓住这个套路就能KO

题目描述:
根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

解题思路:
首先,我们通过前序遍历可以马上得到根节点的值,上例中3即为根节点值。
然后通过根节点的值我们可以在中序遍历中得到他的位置,根节点以左内容为左子树的中序遍历,以右元素是右子树的中序遍历。
得到左右子树的元素个数后,我们又可以返回前序遍历划分出左右子树的前序遍历。
接下来,我们就可以把问题转化为已知左右子树的前序和中序遍历,构造左右子树——是不是很兴奋,递归的套路完成了!
代码实现:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    
private:
    TreeNode* buildTreeRecursive(vector<int>& preorder,vector<int>& inorder,int preStart,int preEnd,int inStart, int inEnd)
    {
    
        //为空节点
        if(preStart > preEnd || inStart > inEnd)
        {
    
            return NULL;
        }
        //先找出根节点和其在中序遍历的位置
        int mid = preorder[preStart];
        TreeNode* root = new TreeNode(mid);
        int midPos = 0;
        for(int i = inStart; i <= inEnd; i++)
        {
    
            if(inorder[i] == mid)
            {
    
                midPos = i;
                break;
            }
        }
        //利用左右子树的节点数量划分前序和中序的左右子树
        int lenLeftTree = midPos - inStart;
        int lenRightTree = inEnd - midPos;
        //左子树为空
        if(lenLeftTree == 0)
        {
    
            root->left = NULL;
        }
        //左子树不为空
        else
        {
    
            root->left = buildTreeRecursive(preorder,inorder,preStart+1,preStart+lenLeftTree,inStart,midPos-1);
        }
        //右子树为空
        if(lenRightTree == 0)
        {
    
            root->right = NULL;
        }
        //右子树不为空
        else
        {
    
            root->right = buildTreeRecursive(preorder,inorder,preStart+lenLeftTree+1,preEnd,midPos+1,inEnd);
        }
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    
        int preStart = 0;
        int preEnd = preorder.size() - 1;
        int inStart = 0;
        int inEnd = preorder.size() - 1;
        TreeNode* ans = buildTreeRecursive(preorder,inorder,preStart,preEnd,inStart,inEnd);
        return ans;
    }
};

轻松惬意,问题解决。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_37477357/article/details/105621947

智能推荐

springboot集成rocketmq_猴子哥哥1024的博客-程序员宝宝_springboot集成rocketmq

  本文是springboot集成rocketmq的入门篇,主要介绍单机环境下安装rocketmq,并集成到springboot框架中,实现字符串类型消息的生产和消费。  1)高可用集群部署方案请参考 待更新。。。  2)更多使用方式请参考 待更新。。。一、下载、安装、启动1、下载http://rocketmq.apache.org/dowloading/releases/2、安装...

如何加快按生产订单查找物料凭证的报表的速度 _superying的博客-程序员宝宝

在sap的物料凭证中mseg表中有AUFNR字段对应订单主数据的AUFK的aufnr字段,很多程序员会按照该关系去查找数据,由于mseg表中有AUFNR没有建立索引,查询非常慢。其实订单到物料凭证的关系存在aufm表,通过该表查询速度将快100倍以上。aufm其实就类似sd的索引器。大家以后碰到报表慢,解决的方法首先是考虑sap的有没有对应的索引器表,实在没有才去建索引。

Java写入读出MySQL乱码问题_半岛落枫的博客-程序员宝宝

JSP显示中文乱码的问题,mysql乱码的问题解决的各种方法

异常类型 && spring事务回滚_天空之城B哥的博客-程序员宝宝

使用spring难免要用到spring的事务管理,要用事务管理又会很自然的选择声明式的事务管理,在spring的文档中说道,spring声明式事务管理默认对非检查型异常和运行时异常进行事务回滚,而对检查型异常则不进行回滚操作。那么什么是检查型异常什么又是非检查型异常呢?最简单的判断点有两个:1.继承自runtimeexception或error的是非检查型异常,而继承自exceptio

Settings.System暂存/读取数据_Jason_Lee155的博客-程序员宝宝

在android应用开发的时候,有时候需要要保存一些变量的值,有好几种方法(SharedPreference/DataBase/...),这里就介绍其中一种,保存到系统数据库中。这种处理方式有一定的好处,其他应用也能读取这个值。但是需要注意:需要系统级应用才行。一、数据库的位置在/data/data/com.android.providers.settings/databases/二、创建数据库的实现代码在frameworks\base\packages\SettingsProvide.

随便推点

并发编程系列(四)之Thread类源码分析(一)_程序员劝退师丶的博客-程序员宝宝

环境:JDK1.8(其他版本可供参考) 开发工具: idea其实把注释翻译一遍就可以懂个七七八八的了打开Thread类线程是程序中的执行线程。java虚拟机允许应用程序有多个线程并发执行。每个线程都有优先级。优先级较高的线程是优先于优先级较低的线程执行。每个线程也可以标记为守护进程,也可以不标记为守护进程。每个线程都有一个用于标识的名称。多个线程可能具有相同的名称。如果在未指...

gulp自动化开发_唯美清泠的博客-程序员宝宝

前端项目搭建前端我们使用gulp来自动化开发流程.配置好gulp后,可以自动给我们处理好一些工作.比如写完css后,要压缩成.min.css,写完js后,要做混淆和压缩,图片压缩等.这些工作都可以让gulp帮我们完成.安装gulp1.创建本地包管理环境:使用npm init命令在本地生成一个package.json文件,package.json是用来记录你当前这个项目依赖了哪些包,以后别人...

reactHooks简单入门教程_凉生可可的博客-程序员宝宝

useState的使用在reactHooks中useState代替了原本的state,const [age,setAge]=useState(18)定义 age的初始值为18通过setAge修改age的值import React ,{ useState} from 'react'function example(){ const [age,setAge]=useState(18)...

idea引入外部jar包的方法_哪 吒的博客-程序员宝宝_idea导入外部jar包

???? Java学习路线配套文章:Java学习路线总结,搬砖工逆袭Java架构师(全网最强)???? 基础推荐:Java基础教程系列???? 实战推荐:Spring Boot基础教程???? 简介:Java领域优质创作者????、CSDN哪吒公众号作者 、Java架构师奋斗者???????? 扫描主页左侧二维码,加入群聊,一起学习、一起进步???? 欢迎点赞 ???? 收藏 留言 ????目录1、下载需要的jar包2、先将下载好的jar包放到resources/lib路径下3、点击Fil

初识 Kubernetes API 的组织结构_米开朗基杨的博客-程序员宝宝

前言话说自己入坑云原生也有好几年了,但是对 kubernetes 基础认识却不够深,导致写代码的时候经常需要打开 godoc 或者 kubernetes 源码查看某个接口或者方法的定义。这...

HTML5中的datalist标签_向前看傻帽儿的博客-程序员宝宝

标签规定了 元素可能的选项列表。 标签被用来在为 元素提供"自动完成"的特性。用户能看到一个下拉列表,里边的选项是预先定义好的,将作为用户的输入数据。请使用 元素的 list 属性来绑定 元素。&lt;!DOCTYPE html&gt;&lt;html&gt;&lt;head&gt; &lt;meta charset="utf-8"&gt; &lt;title&gt;&lt...

推荐文章

热门文章

相关标签