算法框架思维

数据结构和算法学习指南

数据结构的存储方式只有两种： 数组（顺序存储）和链表（链式存储）

对于任何数据结构，基本操作无非 遍历 + 访问，具体一点就是CRUD（增删改查）。

数据结构种类很多，其目的都是在不同的应用场景，尽可能高效的增删改查。

遍历 + 访问 无非两种形式：线性的和非线性的。

线性的就是for/while 迭代为代表，非线性的就是递归为代表。具体一点无非以下几种框架：

1. 数组遍历框架，典型的线性迭代结构

   void traverse(int[] arr) {
     for (int i = 0; i < arr.length; i++) {
       // 迭代访问arr[i]
     }
   }
   

2. 链表遍历框架，兼具迭代和递归结构

   // 单链表节点
   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);
   }
   

3. 二叉树遍历框架，典型的非线性递归结构

   // 二叉树节点
   class TreeNode {
     int val;
     TreeNode* left;
     TreeNode* right;
   };
      
   void traverse(TreeNode* root) {
     // 前序遍历位置
     traverse(root->left);
     // 中序遍历位置
     traverse(root->right);
     // 后序遍历位置
   }
      
   

4. 二叉树扩展为N叉树遍历框架

   // N 叉数节点
   class TreeNode{
     int val;
     TreeNode[] children;
   };
      
   void traverse(TreeNode root) {
     for (TreeNode child: root.children) {
       traverse(child)
     }
   }
   

   N叉数遍历还可以扩展为图的遍历

所谓框架，就是套路。不管增删查改，这些代码都是永远无法脱离的结构，你可以把这个结构作为大纲，根据具体问题在框架上添加代码就行了

刷题建议：

先刷二叉树，先刷二叉树，先刷二叉树， 因为二叉树是最容易培养框架思维的，而且大部分算法技巧（动态规划，分治，回溯等），本质上都是树的遍历问题。