【LeetCode】二叉树刷题总结（三）105、144、199、

简书内代码已上传GitHub：点击我 去GitHub查看代码
写在前面： 写第三次刷题总结了，感觉二叉树的经典题目还可以做好久...因为真的多。刷题顺序主要是按照题目出现的频率从高到底来刷的~

自然界中的二叉树

封印木 --- 图片来源网络

105. 从前序与中序遍历序列构造二叉树

已知一棵二叉树的前序和中序遍历，能否确定唯一二叉树？ 答案是肯定的。 ---嗯，这是废话，不肯定还做个鬼哦23333

我们来回顾一下 前序遍历的次序 ： root 、 left 、 right , 以及中序遍历的次序：left、root、right 。可以发现前序遍历的第一个一定是当前树根节点， 而我们可以根据这个 根节点在中序遍历中 区分左子树和右子树 。中序遍历中，根节点左侧就是左子树，根节点右侧就是右子树。

除了区分左右子树，同时我们还获得了左子树的先序遍历的长度，根节点在中序遍历中的索引就是左子树的先序遍历长度。获得长度后，接下俩就可以在前序遍历中确定左子树的前序遍历序列和右子树的前序遍历序列。

经过以上的叙述，我们可以得到 左右子树的前序遍历序列和中序遍历序列。那就可以继续得到左右子树他们的子树的前序和中序遍历序列。没错，这里就体现出了 分治的思想 。

所以，我们最后要做的就是在不断细分左右子树的过程中构建二叉树就行啦~ ~~来看看代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// 递归 & 分治
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    // 因为前序、中序的长度相等，其中一个为0时返回NULL即可
    if(preorderSize == 0) return NULL;
    // 创建当前子树根节点
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    // 前序遍历的第一个节点就是根节点
    root -> val = preorder[0];
    // 找到中序遍历中根节点的位置，根节点左侧是左子树，故leftlength是左子树长度
    int leftlength = -1;
    while(inorder[++leftlength] != preorder[0]);
    // 更新前序、中序遍历数组范围，继续生成当前根节点下左右子树
    root -> left = buildTree(preorder + 1, leftlength, inorder, leftlength);
    root -> right = buildTree(preorder + 1 + leftlength, preorderSize - leftlength - 1, inorder + leftlength + 1, inorderSize - leftlength - 1);
    // 返回根节点
    return root;
}

代码十分简洁明了，没什么需要注意的地方。

144. 二叉树的前序遍历

前序遍历嘛......写过很多次了，就是 root 、 left 、 right 的次序，递归思想的话也比较简单，直接放代码：

// 先序遍历 --- 递归
void preorder(struct TreeNode* root, int** res, int* returnSize){
    if(root == NULL) return;
    // 存入节点值并更新*returnSize
    *(*res + (*returnSize)++) = root -> val;
    preorder(root -> left, res, returnSize);
    preorder(root -> right, res, returnSize);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int* res = (struct TreeNode*)malloc(sizeof(struct TreeNode) * 1000);
    // *returnSize初始值为0
    *returnSize = 0;
    preorder(root, &res, returnSize);
    return res;
}

如果你们认真看题的话，这道题到这并没有结束！！！
题目最后又加了一句话：递归算法很简单，你可以通过迭代算法完成吗？

当然能！！！

还是老方法，不让用递归的系统栈，，，我们就手动弄个栈存储访问过的节点。这时候有个问题，先访问右节点还是先访问左节点？ 肯能有人会说，前序遍历嘛，肯定先访问左节点......可是这是栈呀！！不利用下它的特性岂不是埋没了它...

因为栈后进先出的特性，所以我们先访问右节点，把右节点先压入栈，然后再把左节点入栈。每次迭代时访问栈顶元素，这时候先访问的就是左节点了。当然一开始要把root入栈。

当栈为空的时候，也就意味着遍历完毕了。
下面给出迭代的代码：

//先序遍历 -- 迭代
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int* res = (int*)malloc(sizeof(int) * 1000), top = 0;
    // 使用栈存储节点
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 1000);
    *returnSize = 0;
    if(root == NULL) return NULL;
    // 栈底压入root
    stack[top++] = root;
    while(top != 0){
        // 获取栈顶节点
        root = stack[--top];
        // 存储
        res[(*returnSize)++] = root->val;
        // 右节点先压入栈
        if(root-> right) stack[top++] = root->right;
        // 左节点入栈，优先级 > 右节点
        if(root-> left) stack[top++] = root->left;
    }
    // 释放资源
    free(stack);
    return res;
}

因为迭代的时候栈空间是手动分配的，所以在return前别忘了释放...

199. 二叉树的右视图

这题呢......主要考的就是前序遍历，就看做的时候思路能不能及时找对了。

题目中要求返回的是右侧可以看到的所有节点值，那么右侧能看到，其实就是 每一层的右侧第一个节点 。而右侧第一个节点怎么获得呢，看到题评论区一堆人纠结层序遍历。

其实没必要，因为如果是从右往左的前序遍历每次到达一个新的深度的时候访问的就是当前深度最右的节点，也就是我们能够看到的节点。所以我们做题时只需要记录 当前访问过的最大深度 ，如果当前深度超过最大深度了，把节点值存入数组即可。

代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
// 从右到左 root - right - left 次序遍历
void travel(struct TreeNode* root,int depth, int* returnSize, int* res){
    if(root == NULL) return;
    // 每层最右节点看得见，存入res，更新*returnSize
    if(depth > *returnSize){
        res[*returnSize] = root -> val;
        *returnSize = depth;
    }
    // 遍历 右、左子树
    travel(root -> right, depth + 1, returnSize, res);
    travel(root -> left, depth + 1, returnSize, res);
}

int* rightSideView(struct TreeNode* root, int* returnSize){
    // 初始返回数组大小为0
    *returnSize = 0;
    int* res = (int*)malloc(sizeof(int) * 1000);
    // 初始深度应为1
    travel(root, 1, returnSize, res);
    return res;
}

这段代码中需要注意 树的初始深度 和 当前深度最大值 的存储问题。

449. 序列化和反序列化二叉搜索树

！！！就是这题，做了我整整3小时......如果做的时候能清醒点就可以少花很多时间，所以一定要审题！！！

题目的意思大概是这样的：我丢给你一棵二叉搜索树，你必须接着......不接不行......然后你总不能带着这么大一棵树走吧，所以你要把它先切碎了，装起来...等到达到目的地了，然后我再向你索要这棵二叉树，你必须完完整整的把它给我，所以你又要把这些碎片拼起来...

说的直白点，就是你要把二叉树存在字符串里，然后再把字符串转为二叉树。具体怎么存，怎么转，题目都没要求，它只需要得到一棵和原先一样的二叉树就行了。

首先，给我们一棵二叉树，我们可以很轻松的得到它的先序遍历。而这题麻烦的一点是，char类型无法承受我们枝叶繁茂的二叉树的重量啊... 不，是int类型存入char类型会导致 截断 的发生。所以不能直接存储，所以我们要思考其他的存储方式。

我们可以用一个字符类型存储节点值的一位，这样我们只需要将节点值按位划分，存入字符串。这时候要记得用一个标识符区分不同节点值。

通过努力，我们还是可以很顺利的得到很畸形的存储于字符串内的二叉树的先序遍历......然后呢，通过先序遍历我们怎么得到一棵二叉树？？正常人都会说 不可能！！！ 然而，这题的二叉树可不是随随便便的二叉树，它是二叉搜索树。

二叉搜索树的中序遍历就是节点值的排序...嗯！！中序遍历，想到这里大概就能反应过来，我们可以把前面得到的前序字符串进行排序...强烈建议先转为整型数组再排序...排完后我们就得到了它的中序遍历。

有了前序和中序遍历，那这道题其实就变成了刚刚前面讲解的 105题：从前序与中序遍历序列构造二叉树 ，接下来也就迎刃而解了！

代码如下：(它就是这么长...90多行...)

#define N 100000
void store(int val, char* res) {
    // 获取res当前长度
    int len = strlen(res);
    // 存储当前值
    char tmp[N] = {0};
    // 工作指针
    int pos = 0;
    while (val > 0) {
        // 按位划分val
        int div = val % 10;
        // 更新写入位置 sprintf() 返回值是成功写入的长度
        pos += sprintf(tmp + pos, "%d", div);
        val = val / 10;
    }
    // 保存长度， 避免重复计算
    int tmplen = strlen(tmp);
    // 写入res串
    for (int i = tmplen - 1; i >= 0; i--) {
        res[len + tmplen - 1 - i] = tmp[i];
    }
    // val间以#分隔
    strcat(res, "#");
    return;
}
// 先序遍历
void preorder(struct TreeNode* root, char* res) {
    if (root == NULL) return;
    // 将val用字符串存储
    store(root -> val, res);
    preorder(root -> left, res);
    preorder(root -> right, res);
    return;
}

// 序列化
char* serialize(struct TreeNode* root) {
    char* res = (char*)calloc(N, sizeof(char));
    // 先序遍历
    preorder(root, res);
    return res;
}

// 递归 & 分治
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    // 因为前序、中序的长度相等，其中一个为0时返回NULL即可
    if(preorderSize == 0) return NULL;
    // 创建当前子树根节点
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    // 前序遍历的第一个节点就是根节点
    root -> val = preorder[0];
    // 找到中序遍历中根节点的位置，根节点左侧是左子树，故leftlength是左子树长度
    int leftlength = -1;
    while(inorder[++leftlength] != preorder[0]);
    // 更新前序、中序遍历数组范围，继续生成当前根节点下左右子树
    root -> left = buildTree(preorder + 1, leftlength, inorder, leftlength);
    root -> right = buildTree(preorder + 1 + leftlength, preorderSize - leftlength - 1, inorder + leftlength + 1, inorderSize - leftlength - 1);
    // 返回根节点
    return root;
}

// 反序列化
struct TreeNode* deserialize(char* data) {
    // 获取字符串长度
    int len = strlen(data);
    // 初始值设为0 NULL
    int val = 0;
    struct TreeNode* root = NULL; 
    int nums[10000];
    int k = 0;
    // 转整型数组
    for (int i = 0; i < len; i++) {
        if (data[i] == '#') {
            nums[k++] = val;            
            val = 0;
        }else{
            val = val * 10 + data[i] - '0';
        }
    }
    // 已知长度，定义第二个数组存放排序后数据
    int nums1[k + 1];
    for(int i = 0; i < k; ++i) nums1[i] = nums[i];
    
    // 冒泡sort
    for(int i = 0; i < k - 1; ++i){
        for(int j = 0; j < k - i - 1; ++j){
            if(nums1[j] > nums1[j + 1]){
                nums1[j] = nums1[j] ^ nums1[j + 1];
                nums1[j + 1] = nums1[j] ^ nums1[j + 1];
                nums1[j] = nums1[j] ^ nums1[j + 1];
            }
        }
    }
    // 通过前序&中序遍历结果生成二叉树
    return buildTree(nums,k,nums1,k);
}

在进行序列化的时候，才发现自己对字符串的操作有多陌生...比如sprintf() 字符串格式化输入，返回成功写入的长度，用的少了就不大清楚了。

669. 修剪二叉搜索树

这题看题目就很难的样子...但是看完修剪的条件，其实很简单。

因为二叉搜索树左子树的所有值都小于根节点，对于根节点来说，它只需要进行以下的更新：

• 根节点值小于L的话，根节点和左子树都需要删除，所以直接返回右节点。

• 根节点值大于R的话，根节点和右子树都需要删除，所以直接返回左节点。

• 根节点值在区间范围内，那么直接返回根节点，这时候要考虑删除的就是根节点的左右子树的部分分支了。同样的步骤，递归就行了。

下面给出代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// 修剪二叉搜索树
struct TreeNode* trimBST(struct TreeNode* root, int L, int R){
    if(root == NULL) return NULL;
    // 更新左子树
    root -> left = trimBST(root -> left, L, R);
    // 更新右子树
    root -> right = trimBST(root -> right, L, R);
    // 更新根节点
    if(root -> val < L) return root -> right;
    else if(root -> val > R) return root -> left;
    else return root;
}

这其实就是 后续遍历，在遍历过左右节点后再比较root与区间范围，从而决定返回的节点。

如果有看不懂的，私信我！！！
~_^^
每天进步一点，加油！

End

END