【JS算法】JS数据结构

JS的数据结构就2种，数组和链表
链表可以演变成：树形结构、图形结构
数组可以演变成：队列、栈
树形结构是前端最重要的数据结构

数组和链表 在内存的存储

数组：是由相同类型的元素的集合所组成的数据结构，分配一块连续的内存来存储。知道第一个元素的内存地址，加上下标（偏移量）就能找到第2或N个。
数组随机访问的速度快，增加和删除则慢（因为删除index2，后面的3-n都要往前挪一位）

链表：非连续存储的指向型存储，随机访问的速度慢（需一层层查找），增加和删除则快（不需要挪位）

---

链表

树形结构、图形结构

树形结构又指向其他树点，就是图形结构
图结构，在webpack和vite中有用到，作用是，能找出是否有文件被重复加载

---

数组

堆和栈

对象

对象是数组+链表的结构

---

来看104题

给定一个二叉树，找出其最大深度
示例： [3,9,20,null,null,15,7]

var maxDepth = function(root) {
    //终止条件
    if(root==null){
        return 0
    }
    //树最大深度，等于左子树的深度和右子树的深度，最大的那一个+1
    return Math.max(maxDepth(root.left),maxDepth(root.right))+1  //递归
};

只要是树形结构，解答基本都可以用递归解决

接着看 力扣上226题

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点

var invertTree = function(root) {
    if(root===null){
        return root
    }
    //递归子问题
    [root.left,root.right] = [invertTree(root.right), invertTree(root.left)]
    console.log(root,root.left,root.right)
    return root
};