二叉树实战
知识补充
（如果不是我这种对二叉树没什么概念的小菜鸡，直接到最底下去看看 [105]从前序与中序遍历序列构造二叉树的解题思路吧！）
在刷这道题之前，我们应该理解一下如何快速的从前序遍历、中序遍历、后序遍历【1】
前序遍历:
前序遍历的遍历方式呢：根、左、右（根节点、和他的左右节点）
中序遍历:
中序遍历的遍历方式呢：左、根、右
后序遍历:
中序遍历的遍历方式呢：左、右、根
根据这个规则我们利用下面的这个例子简单的来做一个练习：
根据下面的二叉树，快速进行前序、后序、中序的序列遍历吧：
前序（根、左、右）：A B C D E F G H I
中序（左、根、右）：C B D A G F H E I
后序（左、右、根）：C D B G H F I E A
实战
光说不练假把式，说了这么多，没有用js实现都是纸上谈兵
二叉树的构造函数
function TreeNode(val, left, right) { this.val = (val===undefined ? 0 : val) this.left = (left===undefined ? null : left) this.right = (right===undefined ? null : right)}前序遍历
二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 **遍历。
输入：root = [1,null,2,3] 输出：[1,2,3]
输入：root = [] 输出：[]
输入：root = [1] 输出：[1]
输入：root = [1,2] 输出：[1,2]
那么这道题的解题思路就很简单了
按照根-左-右的方式进行遍历就好
var preorderTraversal = function(root) { const res = [] preorder(root, res) return res};const preorder = (root, res) => { if(root == null){ return } res.push(root.val) preorder(root.left, res) preorder(root.right, res)}中序遍历
94. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
输入：root = [1,null,2,3] 输出：[1,3,2]
输入：root = [] 输出：[]
输入：root = [1] 输出：[1]
按照左、根、右的方式进行遍历就好
var inorderTraversal = function (root) { const res = [] inorder(root, res) return res};const inorder = (root, res) => { if (root == null) { return } inorder(root.left, res) res.push(root.val) inorder(root.right, res)}仔细一看代码有没有一种？？？似曾相识的感觉？ 不错，我们就仅仅换了一个位置罢了！
后序遍历
145. 二叉树的后序遍历
一样我们记住公式和顺序，换汤不换药
按照 左、右、根
var postorderTraversal = function(root) { const res = [] postorder(root, res) return res};// 按照左、右、根的顺序来就好const postorder = (root,res) => { if(root === null){ return } postorder(root.left, res) postorder(root.right, res) res.push(root.val)}到这里我们的前中后遍历大家就都应该简单懂了吧！
接下来。。。。。重头戏上场！
从前序与中序遍历序列构造二叉树
给定两个整数数组 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]
思路
我们需要紧紧抓住前序遍历序列和中序遍历序列的定义
前序遍历序列的第一个元素就是树的根节点
前序遍历的节点元素的后面的元素 先是左子树的所有节点而后是右子树的所有节点
3 是二叉树的根节点
[9] 则是 二叉树的左子树的所有节点
[20,15,7]是右子树的所有节点
用示例 1举个例子[3,9,20,15,7]
中序遍历中，根节点把中序遍历序列分成了两个部分，左边部分构成了二叉树的根节点的左子树，右边则是右子树
3 是二叉树的根节点
[9] 则是 二叉树的左子树的所有节点
[15,20,7]是右子树的所有节点
举示例 1个例子[9,3,15,20,7]
那我们的思路就有了：
我们可以根据当前前序遍历的第一个元素获取当前二叉树的根节点
利用二叉树的根节点 找到中序遍历的时候的位置，在中序遍历和前序遍历的时候，也就是节点的位置不同，但是左右节点的个数是相同的
这样我们就能确定他的左节点有多少，和右节点有多少个
这样我们就可以通过 parentIndex = inorder.indexOf(preorder[0]) 来获取切分左右节点的个数的位置
左节点：preorder.slice(1, parentIndex + 1)
右节点：preorder.slice(parentIndex + 1)
解法
var buildTree = function(preorder, inorder) { if(inorder.length === 0 || preorder.length === 0){ return null } const res = new TreeNode(preorder[0]) const parentIndex = inorder.indexOf(preorder[0]) res.left = buildTree(preorder.slice(1, parentIndex + 1), inorder.slice(0, parentIndex)) res.right = buildTree(preorder.slice(parentIndex + 1), inorder.slice(parentIndex + 1)) return res};解析：
我们通过slice 每次就传入当前节点的左/右子节点元素的数组,所以我们可以确定，前序序列的数组的第一项肯定就是当前这个二叉树节点的根节点。
利用这个根节点我们通过查询中序序列的位置，我们可以得到这个根节点的左/右节点数组。
递归查询，即可
知识点归纳
【1】前序遍历 中序遍历 后序遍历
【2】105. 从前序与中序遍历序列构造二叉树 Construct Binary Tree from Preorder and Inorder Traversal
优秀博文推荐
东哥带你刷二叉树
原文：https://juejin.cn/post/7101685412069900301