图解Leetcode链表&二叉树相关题

前言

最近也刷了点leetcode的题目，画了几页草稿纸，一边画一边分析，发现过程还是挺有意思的，拿出几题正经的画了画图，也算加深理解了，主要还是链表、二叉树有关的。可能是个人习惯，都是用C语言实现的，先定义俩数据结构，就直接开始了。

struct ListNode {
    int val;
    struct ListNode *next;
};

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};
复制代码

二叉树右视图

leetcode199：给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

分析：
从右边看，其实就是层序遍历，而我们能看到的是每一层最右边的节点。

执行步骤：

1. 层序遍历一般用队列实现，先将root入队列
2. 计算当前队列大小，也就是上一层中节点的数量queueSize
3. 循环取出队列节点，同时将左右子节点入队列，判断是最后一个取出的节点，加入到返回结果中
4. 循环2、3步骤，直到队列空了。

int* rightSideView(struct TreeNode* root, int* returnSize){
    * returnSize = 0;
    if (root == NULL) return NULL;

    int *res = malloc(sizeof(int));

    struct TreeNode **queue = malloc(sizeof(struct TreeNode *) * 10000);
    int head = 0; // 队头
    int tail = 0; // 队尾
    queue[tail++] = root; // 1、先加入根节点root

    while (head < tail) {
        int size = tail - head; // 2、计算当前队列size
        for (int i = 0; i < size; i++) { 
            struct TreeNode *node = queue[head++]; // 3.1、取出队列节点
            if (i == size - 1) { // 3.2、最右一个节点加入res
                res[(*returnSize)++] = node->val;  
                res = realloc(res, sizeof(int) * ((*returnSize) + 1));
            }
            // 3.3、将左右子节点加队列
            if (node->left) queue[tail++] = node->left;
            if (node->right) queue[tail++] = node->right;
        }
    }
    return res;
}
复制代码

Top K问题

leetcode215：无序数组中找到第K大的数，并返回。

分析：首先想到将数组排序，然后取出arr[size - k]的元素。这里考虑使用二叉堆来解决，只需将k个元素排序即可，二叉堆也是二叉树的一种，特点是任意节点的值大于其子节点的值，根节点是最大值。

• 这个数组是二叉树的层序遍历，所以需要把这个数组想象成一颗二叉堆，根据堆的特点移动最大值到根节点（也就是数组的第一个元素），获取最大值，并重复K次。
• 移动节点这里使用二叉堆的上滤，节点和其左右节点比较，如果子节点大于父节点，将二者交换位置，意味是从二叉树的由底至顶的第一个非叶子节点开始，因为要和子节点比较，叶子节点是没有子节点的。
• 时间复杂度：O(nLogN)

执行步骤：

1. 建立二叉堆，第一个非叶子节点的索引通过数组长度得到size/2 - 1， 从下往上的对[0, size/2 - 1]闭区间内的节点执行一次上滤，获得最大值。
2. 根据当前节点索引为parent，可得到子节点索引child = parent*2 + 1，parent和较大的子节点比较，如果较大子节点大于parent，则交换父子节点位置。
3. 交换完成后，继续向下移动，parent = child。
4. 循环执行步骤2、3，对[0, size/2 - 1]区间所有节点完成下滤，就完成二叉堆建立。
5. 数组首个元素则为最大值，将首位0和末尾end元素交换位置
6. 排除末尾的最大值，再次对索引[0, end - 1]进行上滤，重复步骤2、3
7. 循环K次执行步骤5、6，最K大的数为arr[size - k]

节点从下往上下滤的过程，对应步骤1、2、3、4

交换最大值，步骤5、6、7

// 下滤
void heapify(int *nums, int start, int end) {
    int parent = start;
    int child = parent*2 + 1;

    while (child <= end) {
        // 获取左右节点中较大的子节点，索引记为child
        if (child + 1 <= end && nums[child + 1] > nums[child]) child++;

        if (nums[parent] < nums[child]) {  
            swap(&nums[parent], &nums[child]);  // 交换父节点和较大子节点位置
            parent = child;       // 继续向下移动
            child = parent*2 + 1;
        } else {
            break; 
        }
    }
}

int findKthLargest(int* nums, int numsSize, int k){
    // 对[0, numsSize/2 - 1]区间内由下到上遍历节点，并对节点进行下滤
    for (int i = numsSize/2 - 1; i >= 0; i--) { 
        heapify(nums, i, numsSize - 1);
    }

    for (int i = 0; i < k; i++) {
        int end = numsSize - 1 - i; // 末尾的索引
        swap(&nums[0], &nums[end]); // 数组首位最大值和末尾交换位置
        heapify(nums, 0, end - 1);  // [0, end - 1]进行下滤，-1是排除当前最大值
    }
    return nums[numsSize - k];
}
复制代码