一、题目大意给定两个整数数组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]提示:1inorder.length==preorder.length-3000preorder和inorder均无重复元素inorder均出现在preorderpreorder保证为二叉树的前序遍历
一、题目大意给定两个整数数组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]提示:1inorder.length==preorder.length-3000preorder和inorder均无重复元素inorder均出现在preorderpreorder保证为二叉树的前序遍历
二叉树的前序、中序、后序遍历的递归版本非常好理解，在这里就不在赘述了。这里主要讲迭代版本。事实上，计算机在进行递归调用时，会隐式的维护一个栈（叫做调用栈，CallStack），调用函数就把局部变量、入参、返回地址（合起来叫做栈帧，StackFrame）一同入栈，从函数返回就出栈。而迭代版本其实就是把这个过程显式的表现出来，手动的去维护这个栈。同时，迭代版本只需要把节点指针入栈出栈，占用的空间也会小一些。前序遍历因为前序遍历的递归版本是所谓的“尾递归”（即递归调用发生在函数体的尾部），将尾递归转换为迭代相对容易一些：voidpostOrder(TreeNode*root){//如果根节点为空，直
二叉树的前序、中序、后序遍历的递归版本非常好理解，在这里就不在赘述了。这里主要讲迭代版本。事实上，计算机在进行递归调用时，会隐式的维护一个栈（叫做调用栈，CallStack），调用函数就把局部变量、入参、返回地址（合起来叫做栈帧，StackFrame）一同入栈，从函数返回就出栈。而迭代版本其实就是把这个过程显式的表现出来，手动的去维护这个栈。同时，迭代版本只需要把节点指针入栈出栈，占用的空间也会小一些。前序遍历因为前序遍历的递归版本是所谓的“尾递归”（即递归调用发生在函数体的尾部），将尾递归转换为迭代相对容易一些：voidpostOrder(TreeNode*root){//如果根节点为空，直
力扣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]解题思路：先序遍历是“根左右”所以先序遍历数组中的第一个元素肯定是整棵树的根节点，中序遍历是“左根右”所以根节点将左子树的节点元素与右子树的节点元素分隔开来。我们
力扣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]解题思路：先序遍历是“根左右”所以先序遍历数组中的第一个元素肯定是整棵树的根节点，中序遍历是“左根右”所以根节点将左子树的节点元素与右子树的节点元素分隔开来。我们
CSP-J初赛中有许多此类题目，普通方法比较耗费时间以至于无法完成后面的题目，所以在这里介绍一下较快的一种方法。Bilibili：Link额，视频没有字幕，在学校的话没有耳机并不方便，这里手敲出来做法：注意，本文在介绍做法时以已知先序遍历与中序遍历为例；准备：算草纸和笔就够了（还有脑子；首先，将算草纸顺时针旋转90°，在算草纸（旋转后的状态）的第一行写下先/后序遍历的结果，如图：然后，将算草纸逆时针旋转90°，在算草纸（旋转后的状态）的最后一行写下中序遍历的结果，如图：额，下边为了方便书写，将省略“先序”和“中序”等字眼，并且将会把“ABCDE”替换为实例，请注意；把这张图当作平面直角坐标系，
CSP-J初赛中有许多此类题目，普通方法比较耗费时间以至于无法完成后面的题目，所以在这里介绍一下较快的一种方法。Bilibili：Link额，视频没有字幕，在学校的话没有耳机并不方便，这里手敲出来做法：注意，本文在介绍做法时以已知先序遍历与中序遍历为例；准备：算草纸和笔就够了（还有脑子；首先，将算草纸顺时针旋转90°，在算草纸（旋转后的状态）的第一行写下先/后序遍历的结果，如图：然后，将算草纸逆时针旋转90°，在算草纸（旋转后的状态）的最后一行写下中序遍历的结果，如图：额，下边为了方便书写，将省略“先序”和“中序”等字眼，并且将会把“ABCDE”替换为实例，请注意；把这张图当作平面直角坐标系，
