“
本篇文章是自己之前刷剑指Offer的题解总结，分为7个部分，每个部分会单独介绍一些基础概念，然后是具体的题解及思路，在遇见比较相似的题型或思路时会有所归纳方便记忆。
文章较长，希望有用！希望看到最后（看到最后算我输????）！
”“
每道题解分为题目描述、知识点、解题思路、解题代码四个部分，比较重要的部分也会涉及时间空间复杂度等。
”“
本篇文章比较适用于正在刷算法题的同学，提供一个还算不错的思路，每个部分也有基础归纳，会适合于对数据结构0基础的同学理解。
接下来先看目录??
”树“
一种分层数据的抽象模型
”满二叉树：
如果一棵深度为k的二叉树其节点数为2-1那么这棵树便是满二叉树，也就是说除了叶节点以外，其他节点都有两个子节点。
完全二叉树：
满二叉树是一种特殊的完全二叉树，在满二叉树的基础上，除了倒数第二层不是两个子节点，其他节点均有两个子节点，且最下层的节点都集中在左边。
二叉树的结构：使用js的Array与Object构建一棵树
consttree={val:"a",children:[{val:"b",children:[{val:"d",children:[]},{val:"e",children:[]}]},{val:"c",children:[{val:"f",children:[]},{val:"g",children:[]}]}]}二叉树（本质是对象的嵌套）
constbt={val:1,left:{val:2,left:{val:4,left:null,right:null},right:{val:5,left:null,right:null}},right:{val:3,left:{val:6,left:null,right:null},right:{val:7,left:null,right:null}}}二叉树的常用操作有：深度、广度优先遍历，先中后序遍历深度优先遍历，其特点是尽可能深的访问二叉树的分支。
constdfs=(root)={//访问根节点console.log(root.val);//对根节点的children挨个进行深度优先遍历root.children.forEach(node=dfs(node));//root.children.forEach(dfs);}dfs(tree);广度优先遍历，其特点是优先访问离根节点近的节点，从左子树开始。
constbfs=(root)={//创建一个队列，将根节点入队constqueue=[root];while(queue.length){//将队头出队并访问letqueueTop=queue.shift();console.log(queueTop.val);//将队头的children挨个入队queueTop.children.forEach(node={queue.push(node);})}}先序遍历
//递归版，在做题时使用较多constpreorder=(root)={if(!root)return;//首先访问根节点console.log(root.val);//对根节点的左子树进行先序遍历preorder(root.left);//对根节点的右子树进行先序遍历preorder(root.right);}//使用栈的非递归版constpreorder=(root)={if(!root)return;conststack=[root];while(stack.length){consttmp=stack.pop();console.log(tmp.val);if(tmp.right)stack.push(tmp.right);if(tmp.left)stack.push(tmp.left);}}中序遍历
//递归版constinorder=(root)={if(!root)return;inorder(root.left);console.log(root.val);inorder(root.right);}//非递归版constinorder=(root)={if(!root)return;conststack=[];letp=root;//使用一个指针while(stack.length
p){while(p){stack.push(p);p=p.left;}lettemp=stack.pop();console.log(temp.val);p=temp.right;}}后序遍历（使用较少）
//递归版constpostorder=(root)={if(!root)return;postorder(root.left);postorder(root.right);console.log(root.val);}//非递归版constpostorder=(root)={if(!root)return;conststack=[root];constoutputStack=[];while(stack.length){consttmp=stack.pop();outputStack.push(tmp);if(tmp.left)stack.push(tmp.left);//注意这里和先序遍历不同，是先放右节点if(tmp.right)stack.push(tmp.right);}while(outputStack.length){consttmp=outputStack.pop();console.log(tmp.val);}}62.二叉搜索树的第k个结点题目描述：
给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。
知识点：二叉树的中序遍历解题思路：通过观察我们可以发现，这课二叉树的中序遍历恰好是按从小到大的顺序排列的，所以这道题实际考察的是二叉树的中序遍历解题代码：递归版
//中序遍历递归版functionKthNode(pRoot,k){//writecodehereif(!pRoot)returnnull;constres=[];constmidOreder=(node)={if(node.left)preOreder(node.left);res.push(node);if(node.right)preOreder(node.right);}preOreder(pRoot)returnres[k-1];}非递归版
//中序遍历非递归版functionKthNode(pRoot,k){//writecodehereif(!pRoot)returnnull;constres=[];conststack=[];letp=pRoot;while(stack.length
p){while(p){stack.push(p);p=p.left;}lettemp=stack.pop();res.push(temp);p=temp.right;}returnres[k-1];}4.重建二叉树题目描述：
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如，给出前序遍历preorder=[3,9,20,15,7]中序遍历inorder=[9,3,15,20,7]返回如下的二叉树：
3/\/\相似题目：
考察对后序遍历的理解
解题思路：此题考查对先序遍历及中序遍历的理解，我们可以发现对于先序遍历来说其第一个值一定为二叉树的根节点此根节点将中序遍历分为左右子树，所以我首先找到中序遍历对应的根节点的索引i左子树为先序遍历的(1，i+1)，中序遍历的(0，i)，右子树为先序遍历的(i+1,length-1)，中序遍历的(i+1,length-1);时间复杂度为O(n)所有的节点都要被创建解题代码：
varbuildTree=function(preorder,inorder){if(!preorder.length
!inorder.length)returnnull;constroot=newTreeNode(preorder[0]);leti=0;for(;iinorder.length;i++){if(preorder[0]===inorder){break;}}root.left=buildTree(preorder.slice(1,i+1),inorder.slice(0,i));root.right=buildTree(preorder.slice(i+1),inorder.slice(i+1));returnroot;};23.二叉搜索树的后序遍历序列题目描述：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：5/\26/\13示例1：输入:[1,6,3,2,5]输出
alse示例2：输入:[1,3,2,6,5]输出:true
来源：力扣（LeetCode）链接：
