剑指 Offer 07. 重建二叉树

题目说明

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

解题思路

可以通过前序遍历的数组获取每个子树的根节点，并在中序遍历的数组中找到根节点对应的位置，然后就可以确定左右子树的长度mid_root - mid_left，当pre_left > pre_right或者pre_left大于等于数组长度时则说明已经结束啦

通过HashMap可以快速定位到子树根节点在数组中对应的位置

剑指 Offer 16. 数值的整数次方

题目说明

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

解题思路

快速幂法

快速幂法是一种算法，用于在 O(logn) 的时间复杂度内计算一个数的 n 次幂（aⁿ）。该方法基于指数的二进制表示，并使用了 "平方-乘" 的技术来减少所需的乘法操作数。

其实就是将2^n转换成

从而x不断去乘x，b不断的除以2

while (b > 0) {
    if ((b & 1) == 1) { // 奇数
        res *= x;
    }
    x *= x;
    b >>= 1;
}

剑指 Offer 37. 序列化二叉树

题目说明

请实现两个函数，分别用来序列化和反序列化二叉树。

你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

解题思路

本题采用的是前序遍历的方法进行序列化和反序列化

serialize

要注意开头和结尾是“[”和“]”，中间用“,”分隔开

传参是一棵树，在传入参数的时候如果是空直接返回[]，其他的就正常的前序遍历，注意空值的时候

deserialize

传进来的同样是[, , ,]的形式，需要去头尾并用split函数进行分割，用i来维护最新的节点，越界则说明树已经完全形成

用队列来维护前序的节点，若节点非空则进入队列并加入当前节点的左树或者右树