很多朋友害怕算法，其实大可不必，算法题无非就那几个套路，一旦掌握，就会得心应手。
人们常说，在学习算法的过程中，离不开刷题，但是比起刷更多的题，我们更应该学会如何有效的刷题，把握问题的共性和本质，也就是所谓的“框架思维”。
我们知道，数据结构千奇百怪，例如哈希表、栈、队列、图、树、堆等等，但是数据结构的底层存储方式只有两种：数组（顺序存储）和链表（链式存储）。
为什么这样说？那是因为那些多样化的数据结构，究其源头，都是在链表或者数组上的特殊操作，API特性不同而已。比如说，“队列” “栈” 这两种数据结构，既可以用数组实现，也可以使用链表实现，用数组实现，就是处理扩容和缩容的问题；用链表实现，则没有这种问题，但是需要更多的空间存储节点指针。
二者优缺点如下：
数组：由于是紧凑连续存储，因此可以随机访问，通过索引快速找到对应的元素，而且相对节约存储空间。但是由于连续存储，对应的内存空间必须一次性分配足，抑或是在数组中间进行插入或者删除操作，每次必须搬运后面的所有元素，时间复杂度为O(n)。
链表：因为元素不连续，所以不存在数组的扩容和缩容问题，可以方便的进行插入和删除操作，时间复杂度为O(1)，但是无法随机访问，且消耗了相对更多的存储空间。
对于任何数据结构，其基本操作无非遍历+访问，再具体一点就是增，删，查，改。
数据结构有很多，但他们存在的目的无非就是在不同的应用场景下尽可能高效地增删查改。
那么如何对数据结构进行遍历+访问操作呢？无非就是两种形式：线性和非线性。
线性形式以for/while为代表，非线性以递归为代表。
数组遍历框架，是典型的线性迭代框架：
void traverse(int[] arr){
for(int i = 0;i<arr.length;i++){
//迭代访问arr[i]
}
}链表遍历框架，兼具迭代和递归结构：
//基本的单链表结构
class ListNode{
int val;
ListNode next;
}
void traverse(ListNode head){
for(ListNode p = head;p != null; p = p.next){
//迭代遍历p.val
}
}
void traverse(ListNode head){
//前序遍历head.val
traverse(head.next);
//后序遍历head.val
}二叉树遍历框架，是典型的非线性递归遍历结构：
class TreeNode{
int val;
TreeNode left,right;
}
void traverse(TreeNode root){
//前序遍历
traverse(root.left);
//中序遍历
traverse(root.right);
//后序遍历
}不难发现二叉树的递归遍历方式和链表的递归遍历方式十分相似，可以说，即便再多几条叉，递归遍历方式也是一样的。
//N叉树节点
class TreeNode{
int val;
TreeNode[] children;
}
void traverse(TreeNode root){
for(TreeNode child : root.children)
traverse(child);
}因此我们不难发现，所谓框架思维，就是套路。不管增删查改，这些代码都是无法脱离的结构，你可以把这些代码作为大纲，根据具体问题在框架上添加代码就可以了。
树是数据结构中的重中之重，尤其以各类二叉树为学习的难点。同时二叉树问题是所有算法问题中最容易培养框架思维的，因此我们将首先深入学习有关二叉树遍历的问题。
（注：有关二叉树的基本知识点不会在本文过多称述，可以自行搜索）
树是n（n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中： 1）有且仅有一个特定的称为根（Root）的结点； 2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、......、Tn，其中每一个集合本身又是一棵树，并且称为根的子树。
此外，树的定义还需要强调以下两点： 1）n>0时根结点是唯一的，不可能存在多个根结点，数据结构中的树只能有一个根结点。 2）m>0时，子树的个数没有限制，但它们一定是互不相交的。 示例树： 图1.1为一棵普通的树：
由树的定义可以看出，树的定义使用了递归的方式。递归在树的学习过程中起着重要作用，如果对于递归不是十分了解，建议先看看递归算法
有关二叉树的问题，大部分都涉及了二叉树的遍历问题，以下为二叉树遍历通用框架
void traverse(TreeNode root){
//前序遍历
traverse(root.left);
//中序遍历
traverse(root.right);
//后序遍历
}二叉树的遍历是指从二叉树的根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。 二叉树的访问次序可以分为四种：
前序遍历 中序遍历 后序遍历 层序遍历
前序遍历通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。
图2.1 完全二叉树
图2.1所示二叉树访问如下：
从根结点出发，则第一次到达结点A，故输出A; 继续向左访问，第一次访问结点B，故输出B； 按照同样规则，输出D，输出H； 当到达叶子结点H，返回到D，此时已经是第二次到达D，故不在输出D，进而向D右子树访问，D右子树不为空，则访问至I，第一次到达I，则输出I； I为叶子结点，则返回到D，D左右子树已经访问完毕，则返回到B，进而到B右子树，第一次到达E，故输出E； 向E左子树，故输出J； 按照同样的访问规则，继续输出C、F、G；
则3.13所示二叉树的前序遍历输出为： ABDHIEJCFG
中序遍历就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。
图2.1所示二叉树中序访问如下：
从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H； 到达H，H左子树为空，则返回到H，此时第二次访问H，故输出H； H右子树为空，则返回至D，此时第二次到达D，故输出D； 由D返回至B，第二次到达B，故输出B； 按照同样规则继续访问，输出J、E、A、F、C、G；
则图2.1所示二叉树的中序遍历输出为： HDIBJEAFCG
后序遍历就是从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问。
图2.1所示二叉树后序访问如下：
从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H； 到达H，H左子树为空，则返回到H，此时第二次访问H，不输出H； H右子树为空，则返回至H，此时第三次到达H，故输出H； 由H返回至D，第二次到达D，不输出D； 继续访问至I，I左右子树均为空，故第三次访问I时，输出I； 返回至D，此时第三次到达D，故输出D； 按照同样规则继续访问，输出J、E、B、F、G、C，A；
则图2.1所示二叉树的后序遍历输出为： HIDJEBFGCA
//定义节点
typedef struct BiTNode{
TElemType data;//数据
struct BiTNode *lchild, *rchild;//左右孩子指针
} BiTNode, *BiTree;
//前序遍历
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return;
printf("%c", T->data); /*显示结点数据，可以更改为其他对结点操作*/
PreOrderTraverse(T->lchild); /*先序遍历左子树*/
PreOrderTraverse(T->rchild); /*最后先序遍历右子树*/
}
//中序遍历
void InOrderTraverse(BiTree T)
{
if(T==NULL)
return;
InOrderTraverse(T->lchild); /*中序遍历左子树*/
printf("%c", T->data); /*显示结点数据，可以更改为其他对结点操作*/
InOrderTraverse(T->rchild); /*最后中序遍历右子树*/
}
//后序遍历
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild); /*先后序遍历左子树*/
PostOrderTraverse(T->rchild); /*再后续遍历右子树*/
printf("%c", T->data); /*显示结点数据，可以更改为其他对结点操作*/
}层序遍历就是按照树的层次自上而下的遍历二叉树。针对图2.1所示二叉树的层次遍历结果为： ABCDEFGHIJ
思路：
二叉树分好多层，因为要按层遍历，所以如果直接采用函数递归的话，一下子就深入层底了，达不到按层的目的。
所以要换一个角度，按照队列顺序输出！算法步骤如下：
1、把根节点A放入队列，此时队列为：A，队列头指针指向A，也就是队列第一个元素
2、把当前队列头指针所指元素的左右儿子放入队列，即将B、C放入队列，此时队列为A B C ，队列头指针向下移一格，此时指向B
3、不断重复2步骤。此时把B的左右儿子取出来放入队尾，队列变为A B C D E，队列头指针后移，指向c，若c没有子节点，队列不再延长；
4、结束条件，队列头指针和为指针重合时，输出最后一个元素，算法结束！
也就是说，把这个队列从头到尾输出一遍，就是按层遍历，这个队列是动态的，只要有子节点，子节点就会不停的加入队尾，但总有子节点没有的时候，所以，队列尾指针肯定有不再移动的时候，而头指针一直在一步一步向下移，总会有首尾指针重合的时候，即标志着算法结束。
对于二叉树的遍历有一类典型题型。 1）已知前序遍历序列和中序遍历序列，确定一棵二叉树。 例题：若一棵二叉树的前序遍历为ABCDEF，中序遍历为CBAEDF，请画出这棵二叉树。 分析：前序遍历第一个输出结点为根结点，故A为根结点。中序遍历中根结点处于左右子树结点中间，故结点A的左子树中结点有CB，右子树中结点有EDF。 如图2.2所示：
图2.2
按照同样的分析方法，对A的左右子树进行划分，最后得出二叉树的形态如图2.3所示：
图2.3
2）已知后序遍历序列和中序遍历序列，确定一棵二叉树。 后序遍历中最后访问的为根结点，因此可以按照上述同样的方法，找到根结点后分成两棵子树，进而继续找到子树的根结点，一步步确定二叉树的形态。 注：已知前序遍历序列和后序遍历序列，不可以唯一确定一棵二叉树。
参考资料：
labuladong的算法小抄
注：本文仅作为算法学习笔记，如有不足之处还请提出