二叉树

常规树

树的前、中、后序遍历？如何使用非递归实现？

非递归则使用一个栈来维护节点的访问顺序

根据中序、后序遍历，还原树的结构？

letcode传送门

先从后序遍历找到根节点，
然后找到根节点在中序遍历中的顺序，其左侧为中序左子树，右侧为中序右子树
根据中序左子树的长度，从后序遍历开始找到后序左子树；后序右子树同理
递归构建左子树和右子树

根据前序、中序遍历还原树的思路基本保持一致。

判断二叉树是否为对称二叉树

二叉树的右子树是二叉树左子树的镜像二叉树。

镜像二叉树：两颗二叉树根结点相同，但他们的左右两个子节点交换了位置。

递归判断node1.left和node2.right以及node1.right与node2.left

翻转二叉树

递归交换二叉树所有节点的左右节点的位置

二叉树的最大、最小深度

一棵二叉树的最大深度等于左子树深度和右子树最大深度的最大值 + 1，因此通过递归处理

最小深度同理

判断树是否为平衡二叉树

平衡二叉树中，每个子树的深度之差不超过1

递归判断左右子树是否为平衡二叉树

二叉搜索树的第k小的节点

二叉搜索树的中序遍历即排序后的节点，因此先中序遍历，然后在返回索引值为k的节点值即可

给定一个数组，判断是否为二叉搜索树的后序遍历

首先确定根节点，为后序遍历的最后一个值
确认左右子树，左子树全部比根节点小，右子树全部比根节点大
递归判断左右子树

BST 二叉搜索树

特性

二叉搜索树（Binary Search Tree，BST）是一种二叉树数据结构，支持高效的搜索、插入和删除操作。

二叉树结构：每个节点最多有两个子节点，分别称为左子节点和右子节点。
有序性：对于每个节点，其左子树中的所有节点的值都小于该节点的值，而其右子树中的所有节点的值都大于该节点的值。这使得通过比较节点值可以快速定位目标值，提高搜索效率。
中序遍历有序：对BST进行中序遍历，可以得到一个按照升序排列的节点值序列。
唯一性：BST中不允许存在重复的节点值。

实现

BST的基本操作包括：

搜索（Search）：在BST中搜索指定值，通过比较节点值和目标值，根据BST的有序性质进行搜索。
插入（Insertion）：将新节点插入到BST中的合适位置，确保树的有序性质不变。
删除（Deletion）：从BST中删除指定值的节点，确保删除后的树仍然是一棵有效的BST。
遍历（Traversal）：通过不同的遍历方式（如中序、前序、后序）访问BST中的所有节点。

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null;
    }

    insert(value) {
        const newNode = new Node(value);
        if (!this.root) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }

    insertNode(node, newNode) {
        if (newNode.value < node.value) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    }

    search(value) {
        return this.searchNode(this.root, value);
    }

    searchNode(node, value) {
        if (node === null) {
            return false;
        }
        if (value < node.value) {
            return this.searchNode(node.left, value);
        } else if (value > node.value) {
            return this.searchNode(node.right, value);
        } else {
            return true;
        }
    }

    // 删除节点
    remove(value) {
        this.root = this.removeNode(this.root, value);
    }

    removeNode(node, key) {
        if (node === null) {
            return null;
        }

        if (key < node.value) {
            node.left = this.removeNode(node.left, key);
            return node;
        } else if (key > node.value) {
            node.right = this.removeNode(node.right, key);
            return node;
        } else {
            // 没有左右子节点的情况
            if (node.left === null && node.right === null) {
                node = null;
                return node;
            }

            // 只有一个子节点的情况
            if (node.left === null) {
                node = node.right;
                return node;
            } else if (node.right === null) {
                node = node.left;
                return node;
            }

            // 有两个子节点的情况
            const aux = this.findMinNode(node.right);
            node.value = aux.value;
            node.right = this.removeNode(node.right, aux.value);
            return node;
        }
    }

    // 辅助方法：找到最小节点
    findMinNode(node) {
        while (node.left !== null) {
            node = node.left;
        }
        return node;
    }

    // 辅助方法：中序遍历
    inOrderTraversal(node, callback) {
        if (node !== null) {
            this.inOrderTraversal(node.left, callback);
            callback(node.value);
            this.inOrderTraversal(node.right, callback);
        }
    }
}

// 示例用法
const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);

console.log("In-order traversal:");
bst.inOrderTraversal(bst.root, (value) => {
    console.log(value);
});

bst.remove(5); // 删除节点5

console.log("In-order traversal after removing node 5:");
bst.inOrderTraversal(bst.root, (value) => {
    console.log(value);
});

console.log("Searching for value 5:", bst.search(5)); // false

平衡二叉树

平衡二叉树是一种特殊的二叉搜索树，确保了树的左右子树的高度差不超过某个固定的值（通常为1）。

常见的平衡二叉树包括AVL树和红黑树。这些树的平衡性质可以保证在最坏情况下也能保持较低的时间复杂度。

线段树

https://leetcode.cn/problems/range-sum-query-mutable/， letcode 307题，第一次了解到线段树
https://www.cnblogs.com/RioTian/p/13409694.html ，这篇文章写得很通透

定义

线段树（Segment Tree）是一种二叉树数据结构，通常用于处理区间查询问题。它可以用来维护一个序列的信息，例如区间最大值、区间最小值、区间和等，常用于维护区间信息的数据结构

线段树通常用于解决范围查询问题，如区间最小值查询、区间求和等。

线段树的根节点表示整个序列的区间，每个节点表示其对应区间的信息。对于每个节点，它的左子节点表示该区间的左半部分，右子节点表示该区间的右半部分，直到叶子节点表示单个元素。

线段树的构建过程通常是递归的，每次将当前区间一分为二，然后递归构建左右子树。构建完成后，可以用树的深度优先遍历将节点按顺序编号，每个节点的编号即为其对应区间的起始位置。

查询操作可以通过递归地向下遍历节点实现，具体过程是将查询区间与当前节点区间进行比较，如果完全包含则直接返回该节点的信息，否则将查询区间一分为二，分别递归查询左右子树，最后将子树返回的信息合并。

更新操作通常也是递归的，对于要更新的位置，需要找到其对应的叶子节点，然后递归向上更新父节点的信息，直到根节点。

线段树的时间复杂度为 $O(n\log n)$ ，其中 $n$ 是序列的长度。线段树常用于解决区间查询问题，如区间最值、区间和、区间覆盖等。

具体作用

线段树可以使用树结构，也可以用数组来存

比如有个列表[1,2,3,4,5]，线段树会通过二叉树保存左右分段的和，这样就可以快速求任何一个区间的和

a = [1,2,3,4,5]
d[1] = sum(1~5) = 15
    d[2] = sum(1~3) = 6
        d[4] = sum(1~2) = 3
            d[8] = sum(1~1) = 1
            d[9] = sum(2~2) = 2
        d[5] = sum(3~3) = 3
    d[3] = sum(4~5) = 9
        d[6] = sum(4~4) = 4
        d[7] = sum(5~5) = 5

可以看见叶子节点就是长度为1的原数组中的元素，父节点保存了对应子节点区间范围的和，核心思想还是二分和分治，现在统计区间内数据就很简单

求区间[1,3]所有元素的和，直接找到对应保存的区间和d[2]即可
求区间[3,5]所有元素的和，虽然没有直接保存3~5但是可以拆分成区间3~3+4~5，即d[5] + d[3]

在不考虑修改的情况下，前缀和也可以快速求某个区间内的元素和，但如果考虑了修改元素，每次变更之后都需要求对应元素之后的前缀和，但线段树只需要修改相关父节点的值即可

从线段树的结构可以看出，需要先构建子节点，才能求出父节点的和，因此可以先从叶子节点开始递归构建

const segmentTree = [];
/**
 * node 线段树中第n个节点索引值
 * s 左区间
 * e 右区间
 * nums 原始数据列表
 */
function build(node, s, e, nums) {
    // 叶子节点就是递归终止条件
    if (s === e) {
        segmentTree[node] = nums[s];
        return;
    }
    const m = s + Math.floor((e - s) / 2); // 二分左右
    build(node * 2 + 1, s, m, nums); // node * 2 + 1 就是左节点
    build(node * 2 + 2, m + 1, e, nums); // node * 2 + 2 就是右节点
    segmentTree[node] = segmentTree[node * 2 + 1] + segmentTree[node * 2 + 2];
}

const nums = [1, 2, 3, 4, 5];

build(0, 0, nums.length - 1, nums);
console.log(segmentTree) // [15, 6, 9, 3, 3, 4, 5, 1, 2]

线段树构建好之后，就可以快速查找某个区间的值了

function rangeSum(left, right){
    return range(left, right, 0, 0, nums.length - 1);
}

// 从父节点向下找到目标区间的值
function range(left, right, node, s, e) {
    if (left === s && right === e) {
        return segmentTree[node];
    }
    const m = s + Math.floor((e - s) / 2);
    if (right <= m) {
        return range(left, right, node * 2 + 1, s, m);
    } else if (left > m) {
        return range(left, right, node * 2 + 2, m + 1, e);
    } else {
        return range(left, m, node * 2 + 1, s, m) + range(m + 1, right, node * 2 + 2, m + 1, e);
    }
}
rangeSum(2,4) // 3~5区间的元素和，12

最后就是更新某个元素的值时，更新线段树中对应父节点的值

function update(index, val) {
    change(index, val, 0, 0, nums.length - 1);
}
function change(index, val, node, s, e) {
    if (s === e) {
        segmentTree[node] = val;
        return;
    }
    const m = s + Math.floor((e - s) / 2);
    if (index <= m) {
        change(index, val, node * 2 + 1, s, m);
    } else {
        change(index, val, node * 2 + 2, m + 1, e);
    }
    segmentTree[node] = segmentTree[node * 2 + 1] + segmentTree[node * 2 + 2];
}

完整代码

var NumArray = function(nums) {
    n = nums.length;
    this.segmentTree = new Array(nums.length * 4).fill(0);
    this.build(0, 0, n - 1, nums);
};

NumArray.prototype.update = function(index, val) {
    this.change(index, val, 0, 0, n - 1);
};

NumArray.prototype.sumRange = function(left, right) {
    return this.range(left, right, 0, 0, n - 1);
};

NumArray.prototype.build = function(node, s, e, nums) {
    if (s === e) {
        this.segmentTree[node] = nums[s];
        return;
    }
    const m = s + Math.floor((e - s) / 2);
    this.build(node * 2 + 1, s, m, nums);
    this.build(node * 2 + 2, m + 1, e, nums);
    this.segmentTree[node] = this.segmentTree[node * 2 + 1] + this.segmentTree[node * 2 + 2];
}

NumArray.prototype.change = function(index, val, node, s, e) {
    if (s === e) {
        this.segmentTree[node] = val;
        return;
    }
    const m = s + Math.floor((e - s) / 2);
    if (index <= m) {
        this.change(index, val, node * 2 + 1, s, m);
    } else {
        this.change(index, val, node * 2 + 2, m + 1, e);
    }
    this.segmentTree[node] = this.segmentTree[node * 2 + 1] + this.segmentTree[node * 2 + 2];
}

NumArray.prototype.range = function(left, right, node, s, e) {
    if (left === s && right === e) {
        return this.segmentTree[node];
    }
    const m = s + Math.floor((e - s) / 2);
    if (right <= m) {
        return this.range(left, right, node * 2 + 1, s, m);
    } else if (left > m) {
        return this.range(left, right, node * 2 + 2, m + 1, e);
    } else {
        return this.range(left, m, node * 2 + 1, s, m) + this.range(m + 1, right, node * 2 + 2, m + 1, e);
    }
}

前缀树

Trie树，也称为前缀树或字典树，是一种多叉树结构，用于存储动态集合中的字符串。

Trie树的每个节点表示一个字符串的字符，从根节点到某个节点的路径构成了一个字符串。

Trie树常用于字符串搜索和前缀匹配等问题。

堆

堆实际上是一种使用数组实现的二叉树，堆常用于实现优先队列等数据结构，具有高效的插入和删除操作。

关于堆的实现和更多应用，参考堆

二叉树 ​

常规树 ​

树的前、中、后序遍历？如何使用非递归实现？ ​

根据中序、后序遍历，还原树的结构？ ​

判断二叉树是否为对称二叉树 ​

翻转二叉树 ​

二叉树的最大、最小深度 ​

判断树是否为平衡二叉树 ​

二叉搜索树的第k小的节点 ​

给定一个数组，判断是否为二叉搜索树的后序遍历 ​

BST 二叉搜索树 ​

特性 ​

实现 ​

平衡二叉树 ​

线段树 ​

定义 ​

具体作用 ​

完整代码 ​

前缀树 ​

堆 ​

二叉树

常规树