框架思维：这是一种什么样的概念呢？

  1. 从整体到细节，学习一种新事物，对它最快的了解是对它建立抽象的概念，从整体上把握它，知道它为什么存在？是一种什么东西？作用原理是什么？如何使用它？然后再开始去了解稍微具体的细节，最后再去关注它的细节。

那么如何从整体上把握数据结构与算法这门课呢？

  1. 首先，先对数据结构有一个抽象的概念，

    1. 它是什么？立即能想到的就是：线性数据结构（栈、队列）和非线性数据结构（树、堆、图），但这只是数据结构的上层建筑（逻辑结构），结构基础（物理存储方式）就两种：数组（顺序存储）、链表（链式存储）。
    2. 它为什么存在？这里指的就是上层建筑为什么存在，因为正常来说，只要数组和链表不就能满足编程的存储和操作数据的要求了吗？为什么还要有那么多的逻辑数据结构呢？那么因为在不同的的应用场景下，使用不同的逻辑数据结构性能是不一样的，因此，数据结构的使命就是，在不同的应用场景下，尽可能高效地增删改查。
    3. 如何使用数据结构？使用数据结构说白了讲就是对数据结构进行操作（增删改查），实现方式是什么呢？就是 遍历 + 访问。
    4. 那么如何对数据结构遍历呢？方式有两种：for/while型的迭代、递归。对于底层是数组的数据结构，通常采用迭代遍历，而对于底层是链表的数据结构，通常迭代+递归同时使用。
    5. 那么数组存储和链表存储的区别是什么呢？
      1. 数组存储优点：
        • 索引随机访问
        • 相对节约存储空间
      2. 数组存储缺点：
        • 扩容问题
        • 插入删除效率慢
      3. 链表存储优点
        • 无扩容问题
        • 插入删除效率高
      4. 链表存储缺点
        • 无法随机访问
        • 节点指针耗费空间

  2. 那么什么是算法呢？数据结构是工具集合，算法就是使用这些工具的方法（为了解决特定问题）

通用代码模板：

上述讲了数据结构遍历方式无非两种：迭代 + 递归

  1. 迭代遍历通用模板，适用于数组和链式存储

    • 数组迭代

      1. void traverse(int[] arr){
      2. for(int i = 0; i < arr.length; i++){
      3. //visit arr[i]
      4. }
      5. }

    • 链表迭代

      1. void traverse(TreeNode root){
      2. for(TreeNode p = root; p != null; p = p.next){
      3.  //迭代访问p.val   
      4. }
      5. }

  2. 递归遍历通用模板，适用于链式存储，仔细观察：链表递归、二叉树递归都是特殊的N叉树，它们的代码结构都是一致的，而图的遍历就是若干N叉树的遍历（加上visited访问数组）。

    • 链表递归

      1. void traverse(TreeNode root){
      2. //递归访问root.val
      3. traverse(root.next);
      4. }

    • 二叉树递归

      1. void traverse(TreeNode root){
      2. //前序preOrder遍历root.val
      3. traverse(root.left)
      4. //中序inOrder遍历root.val
      5. traverse(root.right)
      6. //后序postOrder遍历root.val
      7. }

    • N叉树递归

      1. class TreeNode {
      2. int val;
      3. TreeNode[] children;//N叉孩子节点
      4. }
      5. void traverse(TreeNode root){
      6. //前序preOrder遍历root.val
      7. for(TreeNode child: root.children){
      8. traverse(child);       
      9. }
      10. //后序postOrder遍历root.val
      11. }