《数据结构与算法之美》学习笔记二

前言：本篇文章介绍了一下二叉树中的基本知识点，包括二叉树的种类、二叉树的存储方式以及二叉树的深度和广度优先遍历；以及《数据结构与算法》中对于数组的讲解记录，只记录了本前端能看懂的🤓，还有很多知识点是我看不懂的，后端老师请自行探索吧。

一、二叉树

最近一直在刷《代码随想录》二叉树相关的题目，总结一下非常基本的一些知识点

（一）二叉树的种类

1、满二叉树

二叉树上只有度为0和度为2的节点，并且度为0的节点都在同一层，这样的二叉树叫做满二叉树。

就是所有的节点都满满当当的。假设二叉树的深度为k，那么满二叉树的节点数为 2^k -1

2、完全二叉树

完全二叉树除了最底层没有填满，其他层的节点都是满的。最后一层的节点集中在左侧。

3、二叉搜索树

二叉搜索树是有顺序的树。

对于二叉搜索树的所有节点，如果左子树不为空，那么左子树上所有节点值都小于节点值；如果右子树不为空，那额右子树上所有节点值都大于节点值。

4、平衡二叉树

它是一棵空树，或者左右子树的高度差不超过1

（二）二叉树的存储方式

1、使用指针的链式存储

链式存储就是用 TreeNode 这个数据类型存储，相信大家在刷力扣的时候见过很多次了。

3、使用数组的顺序存储

使用数组存储的顺序是按照层序遍历的顺序

假设节点的索引是 i，那么左节点的索引就是 i*2+1；右节点的索引就是 i*2+2。

（三）二叉树的遍历

神一样的递归三部曲：

1、确定递归的参数和返回值

2、确定递归的终止条件

3、确定递归的单层逻辑

1、深度遍历

深度遍历的前中后序中的前中后，指的是中间节点出现的顺序

（1）前序

就是中左右的顺序

① 递归

const dfs = function (node) {
    if (!node) return;
    // 访问中间节点
    console.log(node);
    dfs(node.left);
    dfs(node.right);
}

② 迭代

前序遍历的访问顺序是 中左右，先访问中节点，使用栈暂存中节点的左右子节点，由于栈是先进后出的，所以应该先加入右节点，后加入左节点

var preorderTraversal = function (root) {
    const ans = [];
    if (!root) return ans;
    const stack = [root];
    while (stack.length) {
        const item = stack.pop();
        ans.push(item.val);
        item.right && stack.push(item.right);
        item.left && stack.push(item.left);
    }
    return ans;
};

（2）中序

顺序是 左中右

① 递归

const dfs = function (node) {
    if (!node) return;
    dfs(node.left);
    // 访问中间节点
    console.log(node);
    dfs(node.right);
}

② 迭代

// 中序遍历 左中右
// 其实递归就是一个模拟的过程
// 要先加左节点就要一直 .left 到达左叶子节点
// 所以要先将路过的节点存到stack里面
// 并且要用指针指向当前节点
var inorderTraversal = function (root) {
    const stack = [];
    const res = [];
    let cur = root;
    while (stack.length || cur) {
        if (cur) {
            stack.push(cur)
            // 一直找 .left
            cur = cur.left;
        } else {
            // 出栈
            const item = stack.pop();
            res.push(item.val);
            cur = item.right;
        }
    }
    return res;
};

（3）后序

顺序是 左右中

① 递归

const dfs = function (node) {
    if (!node) return;
    dfs(node.left);
    dfs(node.right);
    // 访问中间节点
    console.log(node);
}

② 迭代

上面的前序遍历的迭代实现的是 中左右，后序遍历顺序是 左右中，那么只需要先把前序变成 中右左，然后再翻转最后得到的数组就可以了

var postorderTraversal = function (root) {
    const ans = [];
    if (!root) return ans;
    const stack = [root];
    while(stack.length){
        const cur = stack.pop();
        ans.push(cur.val);
        cur.left && stack.push(cur.left);
        cur.right && stack.push(cur.right);
    }
    return ans.reverse();
};

2、广度优先遍历

就是层序遍历，使用队列或者栈暂存

 // 使用队列保存每一层的节点
var levelOrder = function(root) {
    const ans = [];
    if(!root) return ans;
    const queue = [root];
    while(queue.length){
        const len = queue.length;
        for(let i=0;i
            const item = queue.shift();
            ans.push(item.val);
            item.left && queue.push(item.left);
            item.right && queue.push(item.right);
        }
    }
    return ans;
};