QIT Software Studio 算法知识库

左闭右闭区间
- 循环条件 while (left <= right)
- 中间位置 int mid = left + ((right - left) / 2);
- 右边界更新 right = mid - 1;
- 左边界更新 left = mid + 1;
左闭右开区间
- 循环条件 while (left < right)
- 中间位置 int mid = left + ((right - left) >> 1);
- 右边界更新 right = mid;
- 左边界更新 left = mid + 1;

代码实现

C++

左闭右闭区间

int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size()-1;
    while(left<=right){
        int middle = left+((right-left))/2;
        if(nums[middle]<target){
            left = middle+1;
        }else if(nums[middle]>target){
            right = middle-1;
        }else{
            return middle;
        }
    }
    return -1;
}

左闭右开区间

int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size();
    while(left<right){
        int middle = left+((right-left))/2;
        if(nums[middle]<target){
            left = middle+1;
        }else if(nums[middle]>target){
            right = middle;
        }else{
            return middle;
        }
    }
    return -1;
}

Go

左闭右闭区间

func search(nums []int, target int) int {
    left, right := 0, len(nums) - 1
    for (left <= right) {
        mid := left + (right - left) >> 1
        if (nums[mid] > target) {
            right = mid - 1
        } else if (nums[mid] < target) {
            left = mid + 1
        } else {
            return mid
        }
    }
    return -1;
}

左闭右开区间

func search(nums []int, target int) int {
    left, right := 0, len(nums)

    for (left < right) {
        mid := left + (right - left) >> 1
        if (nums[mid] > target) {
            right = mid
        } else if (nums[mid] < target) {
            left = mid + 1
        } else {
            return mid
        }
    }
    return -1;
}

Java

-左闭右闭区间

class Solution {
    public int search(int[] nums, int target) {
       
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                return mid;
            }
            else if (nums[mid] < target) {
                left = mid + 1;
            }
            else { // nums[mid] > target
                right = mid - 1;
            }
        }
        return -1;
    }
}

-左闭右开区间

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                return mid;
            }
            else if (nums[mid] < target) {
                left = mid + 1;
            }
            else { // nums[mid] > target
                right = mid;
            }
        }
        return -1;
    }
}

TypeScript

-左闭右闭区间

function search(nums: number[], target: number): number {
    let mid: number, left: number = 0, right: number = nums.length - 1;
    while (left <= right) {
        mid = left + ((right - left) >> 1);
        if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
};

-左闭右开区间

function search(nums: number[], target: number): number {
    let mid: number, left: number = 0, right: number = nums.length;
    while (left < right) {
        mid = left +((right - left) >> 1);
        if (nums[mid] > target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
};

JavaScript

-左闭右闭区间 [left, right]

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let mid, left = 0, right = nums.length - 1;
    while (left <= right) {
        mid = left + ((right - left) >> 1);
        if (nums[mid] > target) {
            right = mid - 1;  
        } else if (nums[mid] < target) {
            left = mid + 1;  
        } else {
            return mid;
        }
    }
    return -1;
};

-左闭右开区间 [left, right)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let mid, left = 0, right = nums.length;    
    while (left < right) {
        mid = left + ((right - left) >> 1);
        if (nums[mid] > target) {
            right = mid;  
        } else if (nums[mid] < target) {
            left = mid + 1;  
        } else {
            return mid;
        }
    }
    return -1;
};

双指针

前缀和

题目描述

题目链接

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

输入描述第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间下标：a，b （b > = a），直至文件结束。

输出描述输出每个指定区间内元素的总和。

输入示例

5 1 2 3 4 5 0 1 1 3

输出示例

3 9

数据范围：

0 < n <= 100000

前缀和算法

前缀和是一种预处理技术，它可以将多次区间查询的时间复杂度从 O(n) 降低到 O(1)。

基本原理

预处理阶段：
- 创建一个前缀和数组 prefixSum，其中 prefixSum[i] 表示原数组前 i 个元素的和
- 对于原数组 arr，有 prefixSum[i] = prefixSum[i-1] + arr[i-1]（假设数组下标从0开始）
- 通常我们会设 prefixSum[0] = 0，表示前0个元素的和为0
查询阶段：
- 要计算区间 [a, b] 的和，只需计算 prefixSum[b+1] - prefixSum[a]
- 这是因为 prefixSum[b+1] 包含了前 b+1 个元素的和，而 prefixSum[a] 包含了前 a 个元素的和

代码实现

Go

package main

import (
 "bufio"
 "fmt"
 "os"
 "strconv"
)

func main() {
 scanner := bufio.NewScanner(os.Stdin)
 scanner.Split(bufio.ScanLines)

 scanner.Scan()
 n, _ := strconv.Atoi(scanner.Text())

 arr := make([]int, n)
 for i := 0; i < n; i++ {
  scanner.Scan()
  arr[i], _ = strconv.Atoi(scanner.Text())
 }

 prefixSum := getPrefixSum(arr)

 for scanner.Scan() {
  a, _ := strconv.Atoi(scanner.Text())
  scanner.Scan()
  b, _ := strconv.Atoi(scanner.Text())
  sum := prefixSum[b+1] - prefixSum[a]
  fmt.Println(sum)
 }
}

func getPrefixSum(input []int) []int {
 prefixSum := make([]int, len(input))
 prefixSum[0] = 0
 for i, v := range input {
  prefixSum[i+1] = prefixSum[i] + v
 }
 return prefixSum
}

Java

public class IntervalSum {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取数组长度
        int n = scanner.nextInt();
        
        // 创建原始数组
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        
        // 计算前缀和数组
        int[] prefixSum = new int[n + 1];
        prefixSum[0] = 0;
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + arr[i];
        }
        
        // 处理区间查询
        while (scanner.hasNext()) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            
            // 计算区间和
            int sum = prefixSum[b + 1] - prefixSum[a];
            System.out.println(sum);
        }
        
        scanner.close();
    }
}

时间复杂度分析

预处理阶段：O(n)，其中 n 是数组长度
每次查询：O(1)
总体时间复杂度：O(n + q)，其中 q 是查询次数

适用场景

前缀和算法特别适合处理以下场景：

需要频繁查询数组区间和
数组元素不会被修改（静态数组）

如果需要处理动态修改的情况，可以考虑使用树状数组（Binary Indexed Tree）或线段树（Segment Tree）等更高级的数据结构。

Chapter 2 Linked List

链表基础

链表是一种通过指针串联将需要存储的值在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

涉及到的特殊概念
- 头节点
  - 头节点是指链表中第一个节点，它是链表的入口点。
  - 头节点通常包含链表的元数据信息，例如链表的长度、节点的类型等。
  - 头节点可以是一个空节点，也可以包含一些数据。
- 尾节点
  - 尾节点是指链表中最后一个节点，它是链表的结束点。
  - 尾节点通常不包含任何数据，它的指针域指向null。
- 虚拟头节点
  - 虚拟头节点是指链表中一个特殊的节点，它没有实际的数据，只是为了方便链表的操作而存在。
  - 虚拟头节点通常在链表的头部添加，它的指针域指向链表的第一个节点。
  - 虚拟头节点可以简化链表的操作，例如在链表的头部插入节点、删除节点等。
- 虚拟尾节点
  - 虚拟尾节点是指链表中一个特殊的节点，它没有实际的数据，只是为了方便链表的操作而存在。
  - 虚拟尾节点通常在链表的尾部添加，它的指针域指向null。
  - 虚拟尾节点可以简化链表的操作，例如在链表的尾部插入节点、删除节点等。
- 空链表
  - 空链表是指链表中没有任何节点。
  - 空链表通常不包含任何数据，它的指针域指向null。
  - 空链表通常不包含任何数据，它的指针域指向null。

链表的类型

接下来说一下链表的几种类型:

双链表

每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。因此，双链表可以向前查询和向后查询。

链表的操作

删除节点

实现思路

找到待删除节点的上一个节点。
让上一个节点的next指针指向待删除节点的下一个节点。

代码实现

func (l *ListNode) DeleteNode(val int) {
    cur := l
    for cur != nil && cur.Next != nil {
        if cur.Next.Val == val {
            cur.Next = cur.Next.Next
        }
        cur = cur.Next
    }
}

添加节点

实现思路

找到待添加节点的上一个节点。
让待添加节点的next指针指向待添加节点的上一个节点的next指针指向的节点。
让待添加节点的上一个节点的next指针指向待添加节点。

代码实现

func (l *ListNode) AddNode(val int) {
    cur := l
    for cur!= nil && cur.Next!= nil {
        cur = cur.Next
    }
    cur.Next = &ListNode{Val: val}
}

203.移除链表元素

题目链接

题意：删除链表中等于给定值 val 的所有节点。

示例 1：输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]

示例 2：输入：head = [], val = 1 输出：[]

示例 3：输入：head = [7,7,7,7], val = 7 输出：[]

思路

涉及如下链表操作的两种方式：

直接使用原来的链表来进行删除操作。
设置一个虚拟头结点在进行删除操作。

直击使用给出的链表

非头结点

设置cur，遍历指向要删除结点的前一个结点

设置一个指针q，指向要删除结点。

cur->next = cur->next->next;

删除q指向的结点。（java，python会自动清理，无需刻意删除）

删除头结点

设置一个结点指向头结点：q=head;

头结点指向下个结点:head = head->next;

删除q结点（原来的头结点）

直接使用原来的链表来进行移除节点操作：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 删除头结点
        while (head != NULL && head->val == val) { // 注意这里不是if
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }

        // 删除非头结点
        ListNode* cur = head;
        while (cur != NULL && cur->next!= NULL) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        return head;
    }
};

虚拟头结点

虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。

链表添加一个虚拟头结点为新的头结点，此时要移除这个旧头结点元素1。

这样是不是就可以使用和移除链表其他节点的方式统一了呢？

来看一下，如何移除元素1 呢，还是熟悉的方式，然后从内存中删除元素1。

最后呢在题目中，return 头结点的时候，别忘了 return dummyNode->next;，这才是新的头结点

设置一个虚拟头结点在进行移除节点操作：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
        ListNode* cur = dummyHead;
        while (cur->next != NULL) {
            if(cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

设计链表

题目描述

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

MyLinkedList() 初始化 MyLinkedList 对象。
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

思路

如果对链表的基础知识还不太懂，可以看这篇文章：关于链表，你该了解这些！(opens new window)

如果对链表的虚拟头结点不清楚，可以看这篇文章：链表：听说用虚拟头节点会方便很多？(opens new window)

删除链表节点：链表-删除节点

添加链表节点：链表-添加节点

这道题目设计链表的五个接口：

获取链表第index个节点的数值
在链表的最前面插入一个节点
在链表的最后面插入一个节点
在链表第index个节点前面插入一个节点
删除链表的第index个节点

可以说这五个接口，已经覆盖了链表的常见操作，是练习链表操作非常好的一道题目

链表操作的两种方式：

直接使用原来的链表来进行操作。
设置一个虚拟头结点在进行操作。

代码

下面采用的设置一个虚拟头结点

class MyLinkedList {
private:
    int _size;
    LinkedNode* _dummyHead;
public:
    // 定义链表节点结构体
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };

    // 初始化链表
    MyLinkedList() {
        _dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
        _size = 0;
    }

    // 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
    int get(int index) {
        if (index > (_size - 1) || index < 0) {
            return -1;
        }
        LinkedNode* cur = _dummyHead->next;
        while(index--){ // 如果--index 就会陷入死循环
            cur = cur->next;
        }
        return cur->val;
    }

    // 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;
    }

    // 在链表最后面添加一个节点
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newNode;
        _size++;
    }

    // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果index大于链表的长度，则返回空
    // 如果index小于0，则在头部插入节点
    void addAtIndex(int index, int val) {

        if(index > _size) return;
        if(index < 0) index = 0;        
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }

    // 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
    void deleteAtIndex(int index) {
        if (index >= _size || index < 0) {
            return;
        }
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur ->next;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        //delete命令指示释放了tmp指针原本所指的那部分内存，
        //被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，
        //如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针
        //如果之后的程序不小心使用了tmp，会指向难以预想的内存空间
        tmp=nullptr;
        _size--;
    }

    // 打印链表
    void printLinkedList() {
        LinkedNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
};

时间复杂度: 涉及 index 的相关操作为 O(index), 其余为 O(1)
空间复杂度: O(n)

反转链表

题目链接

题意：反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

思路

如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。

其实只需要改变链表的next指针的指向，直接将链表反转，而不用重新定义一个新的链表，如图所示:

206_反转链表

之前链表的头节点是元素1，反转之后头结点就是元素5 ，这里并没有添加或者删除节点，仅仅是改变next指针的方向。

那么接下来看一看是如何反转的呢？

我们拿有示例中的链表来举例，如动画所示：（纠正：动画应该是先移动pre，在移动cur）

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。

然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。

为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。

接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。

最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。此时我们return pre指针就可以了，pre指针就指向了新的头结点。

双指针法

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->next
            cur->next = pre; // 翻转操作
            // 更新pre 和 cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

删除倒数第N个元素

例题

例题链接

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

示例 1：

输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1 输出：[]

示例 3：

输入：head = [1,2], n = 1 输出：[1]

思路

双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。

步骤

首先这里我推荐大家使用虚拟头结点，这样方便处理删除实际头结点的逻辑
定义fast指针和slow指针，初始值为虚拟头结点
fast首先走n + 1步，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作）
fast和slow同时移动，直到fast指向末尾
删除slow指向的下一个节点

代码

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* slow = dummyHead;
        ListNode* fast = dummyHead;
        while(n-- && fast != NULL) {
            fast = fast->next;
        }
        fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点
        while (fast != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next; 
        
        // ListNode *tmp = slow->next;  C++释放内存的逻辑
        // slow->next = tmp->next;
        // delete tmp;
        
        return dummyHead->next;
    }
};

链表相交

题目

题目链接

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须保持其原始结构。

示例 1：

示例 2：

示例 3：

思路

简单来说，就是求两个链表交点节点的指针。这里同学们要注意，交点不是数值相等，而是指针相等。

为了方便举例，假设节点元素数值相等，则节点指针相等。

看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点：

面试题02.07.链表相交_1

我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：

面试题02.07.链表相交_2

此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。

否则循环退出返回空指针。

环形链表II

题目描述

题目链接

题意：给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

循环链表

算法公开课

《代码随想录》算法视频公开课 (opens new window)：把环形链表讲清楚！| LeetCode:142.环形链表II (opens new window)，相信结合视频再看本篇题解，更有助于大家对链表的理解。

思路

这道题目，不仅考察对链表的操作，而且还需要一些数学运算。

主要考察两知识点：

判断链表是否环
如果有环，如何找到这个环的入口

判断链表是否有环

可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇，说明这个链表有环。

为什么fast 走两个节点，slow走一个节点，有环的话，一定会在环内相遇呢，而不是永远的错开呢

首先第一点：fast指针一定先进入环中，如果fast指针和slow指针相遇的话，一定是在环中相遇，这是毋庸置疑的。

那么来看一下，为什么fast指针和slow指针一定会相遇呢？

可以画一个环，然后让 fast指针在任意一个节点开始追赶slow指针。

会发现最终都是这种情况，如下图：

142环形链表1

fast和slow各自再走一步， fast和slow就相遇了

这是因为fast是走两步，slow是走一步，其实相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合。

动画如下：

141.环形链表

如果有环，如何找到这个环的入口

此时已经可以判断链表是否有环了，那么接下来要找这个环的入口了。

假设从头结点到环形入口节点的节点数为x。环形入口节点到 fast指针与slow指针相遇节点节点数为y。从相遇节点再到环形入口节点节点数为 z。如图所示：

那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针，（y+z）为一圈内节点的个数A。

因为fast指针是一步走两个节点，slow指针一步走一个节点，所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：

(x + y) * 2 = x + y + n (y + z)

两边消掉一个（x+y）: x + y = n (y + z)

因为要找环形的入口，那么要求的是x，因为x表示头结点到环形入口节点的的距离。

所以要求x ，将x单独放在左面：x = n (y + z) - y ,

再从n(y+z)中提出一个（y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。

这个公式说明什么呢？

先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。

当 n为1的时候，公式就化解为 x = z，

这就意味着，从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点，那么当这两个指针相遇的时候就是环形入口的节点。

也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。

让index1和index2同时移动，每次移动一个节点，那么他们相遇的地方就是环形入口的节点。

动画如下：

142.环形链表II（求入口）

那么 n如果大于1是什么情况呢，就是fast指针在环形转n圈之后才遇到 slow指针。

其实这种情况和n为1的时候效果是一样的，一样可以通过这个方法找到环形的入口节点，只不过，index1 指针在环里多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
            if (slow == fast) {
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2; // 返回环的入口
            }
        }
        return NULL;
    }
};

时间复杂度: O(n)，快慢指针相遇前，指针走的次数小于链表长度，快慢指针相遇后，两个index指针走的次数也小于链表长度，总体为走的次数小于 2n
空间复杂度: O(1)

Chapter 3 Hash Table

哈希表

哈希表（英文名字为Hash table，国内也有一些算法书籍翻译为散列表，大家看到这两个名称知道都是指hash table就可以了）。

哈希表是根据关键码的值而直接进行访问的数据结构。

这么官方的解释可能有点懵，其实直白来讲其实数组就是一张哈希表。

哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素，如下图所示：

哈希表1

那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。

例如要查询一个名字是否在这所学校里。

要枚举的话时间复杂度是O(n)，但如果使用哈希表的话，只需要O(1)就可以做到。

我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

将学生姓名映射到哈希表上就涉及到了hash function ，也就是哈希函数。

哈希函数

哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。

哈希函数如下图所示，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。

哈希表2

如果hashCode得到的数值大于哈希表的大小了，也就是大于tableSize了，怎么办呢？

此时为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作，这样我们就保证了学生姓名一定可以映射到哈希表上了。

此时问题又来了，哈希表我们刚刚说过，就是一个数组。

如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表同一个索引下标的位置。

接下来哈希碰撞登场

哈希碰撞

如图所示，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞。

哈希表3

一般哈希碰撞有两种解决方法，拉链法和线性探测法。

拉链法

刚刚小李和小王在索引1的位置发生了冲突，发生冲突的元素都被存储在链表中。这样我们就可以通过索引找到小李和小王了

哈希表4

（数据规模是dataSize，哈希表的大小为tableSize）

其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

线性探测法

使用线性探测法，一定要保证tableSize大于dataSize。我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放冲突的数据了。如图所示：

哈希表5

其实关于哈希碰撞还有非常多的细节，感兴趣的同学可以再好好研究一下，这里我就不再赘述了。

常见的三种哈希结构

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

数组
set （集合）
map(映射)

这里数组就没啥可说的了，我们来看一下set。

在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：

集合	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::set	红黑树	有序	否	否	O(log n)	O(log n)
std::multiset	红黑树	有序	是	否	O(logn)	O(logn)
std::unordered_set	哈希表	无序	否	否	O(1)	O(1)

映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::map	红黑树	key有序	key不可重复	key不可修改	O(logn)	O(logn)
std::multimap	红黑树	key有序	key可重复	key不可修改	O(log n)	O(log n)
std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

有效字母异位

例题

例题链接

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = "anagram", t = "nagaram" 输出: true

示例 2: 输入: s = "rat", t = "car" 输出: false

说明: 你可以假设字符串只包含小写字母。

思路

数组其实就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。

注意只有在限制题目数值大小时才能使用数组哈希，而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

定一个数组叫做record，大小为26 就可以了，初始化为0，因为字符a到字符z的ASCII也是26个连续的数值。
为了方便举例，判断一下字符串s= "aee", t = "eae"。
因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。
再遍历字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。
record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。最后如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26] = {0};
        for (int i = 0; i < s.size(); i++) {
            // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
            record[s[i] - 'a']++;
        }
        for (int i = 0; i < t.size(); i++) {
            record[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (record[i] != 0) {
                // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
                return false;
            }
        }
        // record数组所有元素都为零0，说明字符串s和t是字母异位词
        return true;
    }
};

383. 赎金信

题目链接

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

注意：

你可以假设两个字符串均只含有小写字母。

canConstruct("a", "b") -> false canConstruct("aa", "ab") -> false canConstruct("aa", "aab") -> true

思路

这道题目和242.有效的字母异位词 (opens new window)很像，242.有效的字母异位词 (opens new window)相当于求字符串a 和字符串b 是否可以相互组成，而这道题目是求字符串a能否组成字符串b，而不用管字符串b 能不能组成字符串a。

本题判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成，但是这里需要注意两点。

第一点“为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思” 这里说明杂志里面的字母不可重复使用。
第二点 “你可以假设两个字符串均只含有小写字母。” 说明只有小写字母，这一点很重要

暴力解法

那么第一个思路其实就是暴力枚举了，两层for循环，不断去寻找，代码如下：

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        for (int i = 0; i < magazine.length(); i++) {
            for (int j = 0; j < ransomNote.length(); j++) {
                // 在ransomNote中找到和magazine相同的字符
                if (magazine[i] == ransomNote[j]) {
                    ransomNote.erase(ransomNote.begin() + j); // ransomNote删除这个字符
                    break;
                }
            }
        }
        // 如果ransomNote为空，则说明magazine的字符可以组成ransomNote
        if (ransomNote.length() == 0) {
            return true;
        }
        return false;
    }
};

时间复杂度: O(n^2)
空间复杂度: O(1)

这里时间复杂度是比较高的，而且里面还有一个字符串删除也就是erase的操作，也是费时的，当然这段代码也可以过这道题。

哈希解法

因为题目说只有小写字母，那可以采用空间换取时间的哈希策略，用一个长度为26的数组来记录magazine里字母出现的次数。

然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。

依然是数组在哈希法中的应用。

一些同学可能想，用数组干啥，都用map完事了，其实在本题的情况下，使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。所以数组更加简单直接有效！

代码如下：

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26] = {0};
        //add
        if (ransomNote.size() > magazine.size()) {
            return false;
        }
        for (int i = 0; i < magazine.length(); i++) {
            // 通过record数据记录 magazine里各个字符出现次数
            record[magazine[i]-'a'] ++;
        }
        for (int j = 0; j < ransomNote.length(); j++) {
            // 遍历ransomNote，在record里对应的字符个数做--操作
            record[ransomNote[j]-'a']--;
            // 如果小于零说明ransomNote里出现的字符，magazine没有
            if(record[ransomNote[j]-'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};

两个数组的交集

例题

例题链接

题意：给定两个数组，编写一个函数来计算它们的交集。

说明： 输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

思路

学会使用：unordered_set

输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的，同时可以不考虑输出结果的顺序

注意只有在限制题目数值大小时才能使用数组哈希，而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表，使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for (int num : nums2) {
            // 发现nums2的元素 在nums_set里又出现过
            if (nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

两数之和

例题

例题链接

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

思路

什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。

本题数组和set来做哈希法的局限：

数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。

本题需要明确两点：

map用来做什么
map中key和value分别表示什么

元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标

在遍历数组的时候，只需要向map去查询是否有和目前遍历元素匹配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map <int,int> map;
        for(int i = 0; i < nums.size(); i++) {
            // 遍历当前元素，并在map中寻找是否有匹配的key
            auto iter = map.find(target - nums[i]); 
            if(iter != map.end()) {
                return {iter->second, i};
            }
            // 如果没找到匹配对，就把访问过的元素和下标加入到map中
            map.insert(pair<int, int>(nums[i], i)); 
        }
        return {};
    }
};

三数之和

题目链接

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

思路

双指针

其实这道题目使用哈希法并不十分合适，因为在去重的操作中有很多细节需要注意，在面试中很难直接写出没有bug的代码。

而且使用哈希法在使用两层for循环的时候，能做的剪枝操作很有限，虽然时间复杂度是O(n^2)，也是可以在leetcode上通过，但是程序的执行时间依然比较长。

接下来我来介绍另一个解法：双指针法，这道题目使用双指针法要比哈希法高效一些，那么来讲解一下具体实现的思路。

动画效果如下：

15.三数之和

拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。

依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。

接下来如何移动left 和right呢，如果nums[i] + nums[left] + nums[right] > 0 就说明此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明此时三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

时间复杂度：O(n^2)。

C++代码代码如下：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.size(); i++) {
            // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[i] > 0) {
                return result;
            }
            // 错误去重a方法，将会漏掉-1,-1,2 这种情况
            /*
            if (nums[i] == nums[i + 1]) {
                continue;
            }
            */
            // 正确去重a方法
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.size() - 1;
            while (right > left) {
                // 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组
                /*
                while (right > left && nums[right] == nums[right - 1]) right--;
                while (right > left && nums[left] == nums[left + 1]) left++;
                */
                if (nums[i] + nums[left] + nums[right] > 0) right--;
                else if (nums[i] + nums[left] + nums[right] < 0) left++;
                else {
                    result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;

                    // 找到答案时，双指针同时收缩
                    right--;
                    left++;
                }
            }

        }
        return result;
    }
};

第18题. 四数之和

题目链接

题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

思路

四数之和，和三数之和是一个思路，都是使用双指针法, 基本解法就是在三数之和的基础上再套一层for循环。

但是有一些细节需要注意，例如：不要判断nums[k] > target 就返回了，三数之和可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成nums[k] > target && (nums[k] >=0 || target >= 0)就可以了。

三数之和的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下标作为双指针，找到nums[i] + nums[left] + nums[right] == 0。

四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n^2)，四数之和的时间复杂度是O(n^3) 。

那么一样的道理，五数之和、六数之和等等都采用这种解法。

对于三数之和双指针法就是将原本暴力O(n^3)的解法，降为O(n^2)的解法，四数之和的双指针解法就是将原本暴力O(n^4)的解法，降为O(n^3)的解法。

C++代码

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++) {
            // 剪枝处理
            if (nums[k] > target && nums[k] >= 0) {
            	break; // 这里使用break，统一通过最后的return返回
            }
            // 对nums[k]去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {
                // 2级剪枝处理
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;
                }

                // 对nums[i]去重
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
                    if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
                        right--;
                    // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
                    } else if ((long) nums[k] + nums[i] + nums[left] + nums[right]  < target) {
                        left++;
                    } else {
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        // 找到答案时，双指针同时收缩
                        right--;
                        left++;
                    }
                }

            }
        }
        return result;
    }
};

Chapter 1 Binary Tree

理论基础

二叉树是一种非线性数据结构，由节点组成，每个节点最多有两个子节点，通常称为"左子节点"和"右子节点"。

基本概念

节点（Node）：二叉树的基本单位，包含数据和指向子节点的引用
根节点（Root）：二叉树的顶部节点，没有父节点
叶节点（Leaf）：没有子节点的节点
父节点（Parent）：有子节点的节点
子节点（Child）：某节点下一层的节点
兄弟节点（Sibling）：共享同一父节点的节点
节点的度（Degree）：节点的子节点数量
树的高度/深度：从根节点到最远叶节点的最长路径上的节点数
节点的层级（Level）：从根节点到该节点的边的数量加1

二叉树的类型

满二叉树（Full Binary Tree）：每个节点要么有0个子节点，要么有2个子节点
完全二叉树（Complete Binary Tree）：除了最后一层外，其他层都被完全填充，且最后一层的所有节点都尽可能靠左排列
完美二叉树（Perfect Binary Tree）：所有内部节点都有两个子节点，所有叶节点都在同一层
平衡二叉树（Balanced Binary Tree）：任意节点的左右子树高度差不超过1
二叉搜索树（Binary Search Tree）：左子树上所有节点的值都小于根节点的值，右子树上所有节点的值都大于根节点的值

二叉树的性质

第i层的最大节点数为 $2^(i-1)$
深度为k的二叉树最多有 $2^k - 1$ 个节点
任何非空二叉树，若叶节点数为n0，度为2的节点数为n2，则 n0 = n2 + 1
具有n个节点的完全二叉树的高度为 ⌊log₂n⌋ + 1

二叉树的存储结构

链式存储：每个节点包含数据域和指向左右子节点的指针
顺序存储：使用数组存储，对于索引为i的节点，其左子节点索引为2i+1，右子节点索引为2i+2

二叉树的遍历方式

深度优先遍历（DFS）

前序遍历（Preorder）：根 → 左 → 右
中序遍历（Inorder）：左 → 根 → 右
后序遍历（Postorder）：左 → 右 → 根

广度优先遍历（BFS）

层序遍历（Level Order）：按层从左到右遍历所有节点

二叉树的定义

Go

type TreeNode struct {
    Val any
    Left *TreeNode
    Right *TreeNode
}

树的遍历

思路

递归遍历

递归三要素

确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件：写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
确定单层递归的逻辑：确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

迭代遍历

迭代遍历是通过显式使用栈或队列等数据结构来模拟递归过程，避免了系统栈的开销和递归深度限制。

代码实现

前序遍历（根-左-右）

递归遍历

访问根节点
递归遍历左子树
递归遍历右子树

func preOrderTraversal(root *TreeNode) []int {
    result := []int{}
    
    // 定义递归函数
    var traversal func(node *TreeNode)
    traversal = func(node *TreeNode) {
        // 终止条件, 当节点为空时返回
        if node == nil {
            return
        }
        // 访问根节点
        result = append(result, node.Val)
        // 递归遍历左子树
        traversal(node.Left)
        // 递归遍历右子树
        traversal(node.Right)
    }

    // 调用递归函数
    traversal(root)
    return result
}

迭代遍历

初始化一个栈，将根节点入栈
当栈不为空时，执行以下操作：
- 弹出栈顶节点，并访问它
- 将右子节点入栈（如果存在）
- 将左子节点入栈（如果存在）
- 注意：先右后左入栈，因为栈是后进先出的

func preOrderTraversal(root *TreeNode) []int {
    result := []int{}
    if root == nil {
        return result
    }
    
    stack := []*TreeNode{root}
    
    for len(stack) > 0 {
        // 弹出栈顶元素
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        
        // 访问节点
        result = append(result, node.Val)
        
        // 先右后左入栈（因为栈是后进先出）
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
    }
    
    return result
}

中序遍历（左-根-右）

递归遍历

递归遍历左子树
访问根节点
递归遍历右子树

func inOrderTraversal(root *TreeNode) []int {
    result := []int{}
    // 定义递归函数
    var traversal func(node *TreeNode)
    traversal = func(node *TreeNode) {
        // 终止条件, 当节点为空时返回
        if node == nil {
            return
        }
        // 递归遍历左子树
        traversal(node.Left)
        // 访问根节点
        result = append(result, node.Val)
        // 递归遍历右子树
        traversal(node.Right)
    }
    // 调用递归函数
    traversal(root)
    return result
}

迭代遍历

初始化一个栈和一个当前节点指针
当栈不为空或者当前节点不为空时，执行以下操作：
- 如果当前节点不为空，将其入栈，并将当前节点更新为其左子节点
- 如果当前节点为空，弹出栈顶节点，并访问它，然后将当前节点更新为其右子节点

func inOrderTraversal(root *TreeNode) []int {
    result := []int{}
    stack := []*TreeNode{}
    cur := root
    for cur != nil || len(stack) > 0 {
        // 如果当前节点不为空，将其入栈，并将当前节点更新为其左子节点
        if cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        } else {
            // 如果当前节点为空，弹出栈顶节点，并访问它，然后将当前节点更新为其右子节点
            cur = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            result = append(result, cur.Val)
            cur = cur.Right
        }
    }
    return result
}

后序遍历（左-右-根）

递归遍历

递归遍历左子树
递归遍历右子树
访问根节点

func postOrderTraversal(root *TreeNode) []int {
    result := []int{}
    // 定义递归函数
    var traversal func(node *TreeNode)
    traversal = func(node *TreeNode) {
        // 终止条件, 当节点为空时返回
        if node == nil {
            return
        }
        // 递归遍历左子树
        traversal(node.Left)
        // 递归遍历右子树
        traversal(node.Right)
        // 访问根节点
        result = append(result, node.Val)
    }
    // 调用递归函数
    traversal(root)
    return result
}

迭代遍历

初始化一个栈和一个当前节点指针
当栈不为空或者当前节点不为空时，执行以下操作：
- 如果当前节点不为空，将其入栈，并将当前节点更新为其右子节点
- 如果当前节点为空，弹出栈顶节点，并访问它，然后将当前节点更新为其左子节点

func postOrderTraversal(root *TreeNode) []int {
    result := []int{}
    stack := []*TreeNode{}
    cur := root
    for cur!= nil || len(stack) > 0 {
        // 如果当前节点不为空，将其入栈，并将当前节点更新为其右子节点
        if cur!= nil {
            stack = append(stack, cur)
            cur = cur.Right
        } else {
            // 如果当前节点为空，弹出栈顶节点，并访问它，然后将当前节点更新为其左子节点
            cur = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            result = append(result, cur.Val)
            cur = cur.Left
        }
    }
    return result
}

层序遍历

递归遍历

func levelOrder(root *TreeNode) [][]int {
    result := [][]int{}
    
    // 定义递归函数
    var traversal func(node *TreeNode, depth int)
    traversal = func(node *TreeNode, depth int) {
        // 终止条件, 当节点为空时返回
        if node == nil {
            return
        }
        
        // 如果结果列表的长度等于当前深度，则添加一个新的空列表
        if len(result) == depth {
            result = append(result, []int{})
        }
        
        // 将当前节点的值添加到对应深度的结果列表中
        result[depth] = append(result[depth], node.Val)
        
        // 递归遍历左子树和右子树，深度加1
        traversal(node.Left, depth+1)
        traversal(node.Right, depth+1)
    }
    
    // 从根节点开始，深度为0
    traversal(root, 0)
    return result
}

队列

初始化一个队列和一个结果列表
将根节点入队
当队列不为空时，执行以下操作：
- 弹出队首节点，并将其值添加到结果列表中
- 将节点的左子节点和右子节点入队（如果存在）

func levelOrder(root *TreeNode) [][]int {
    result := [][]int{}
    if root == nil {
        return result
    }
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        // 获取当前层的节点数
        levelSize := len(queue)
        // 初始化一个空列表，用于存储当前层的节点值
        level := []int{}
        for i := 0; i < levelSize; i++ {
            // 弹出队首节点
            node := queue[0]
            queue = queue[1:]
            // 将节点的值添加到当前层的列表中
            level = append(level, node.Val)
            // 将节点的左子节点和右子节点入队（如果存在）
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        // 将当前层的节点值添加到结果列表中
        result = append(result, level)
    }
    return result
}

Chapter 15 Greedy Algorithms

确定贪心策略
确定遍历顺序
求解每个子问题的最优解
将子问题的最优解合并为原问题的最优解

QIT Software Studio Algorithm Library