【代码随想录】




一、数组

704.二分查找

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        int center = 0;    // 二分位置
        while (left <= right) {
            center = (left + right) / 2;
            if (nums[center] == target) return center;
            if (nums[center] > target) right = center - 1;
            if (nums[center] < target) left = center + 1;
        }
        // --查找失败--
        return -1;
    }
};
  • 时间复杂度：O(log n)
    分析：2x=n→x=log2n→O(log n)2^x = n \to x = log_2n\to O(log\,n)
  • 空间复杂度：O(1)




27.移除元素

力扣题目链接

1、暴力解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int nowLength = nums.size();  // 记录现在长度
        for (int i = 0; i < nowLength; i++) {
            // --逐个查找--
            if (nums[i] == val) {
                // --删除元素--
                for (int j = i; j < nowLength - 1; j++) {
                    nums[j] = nums[j + 1];
                }
                // --改变上界--
                nowLength--;
                // --由于数组左移，所以再次查看当前位置--
                i--;
            }
        }
        // --返回删除后的长度--
        return nowLength;
    }
};
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)

2、快慢指针：

27.移除元素-双指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int len = nums.size();  // 执行一次
        int slow = 0;
        // --看n次，值为val的舍弃（即需要值不为val的选出来放到新位置（slow）上）--
        for (int fast = 0; fast < len; fast++) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)




977.有序数组的平方

力扣题目链接

1、平方后排序

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int len = nums.size();
        for (int i = 0; i < len; i++) {
            nums[i] = nums[i] * nums[i];
        }
        // --快排--
        sort(nums.begin(),nums.end());
        return nums;
    }
};

时间复杂度：O(nlogn)

2、双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int len = nums.size();
        // --长度为len，初值为0--
        vector<int> ans(len, 0);
        int cnt = len;
        int i = 0, j = len - 1;
        while(i <= j) {
            // --前进左边--
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                ans[--cnt] = nums[i] * nums[i];
                i++;
            }
            // --前进右边--
            else {
                ans[--cnt] = nums[j] * nums[j];
                j--;
            }
        }
        return ans;
    }
};
  • 时间复杂度：O(n)




209.长度最小的子数组

力扣题目链接

快慢指针（滑动窗口）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int len = nums.size();
        int fast = 0, slow = 0;     
        int sum = 0;    // 总和
        int ans = 0x7fffffff;
        for (; fast <= len; fast++) {
            // --和小于target，加上右边--
            if (fast < len && sum < target) {
                sum += nums[fast];
                // printf("[sum:%d slow:%d, fast:%d, ans=%d]\n", sum, slow, fast, ans);
                continue;
            }
            // --和大于等于target，最小值更新；减去左边，slow向前移动，fast暂时不动--
            if (sum >= target) {
                ans = (fast - slow) < ans ? (fast - slow) : ans;
                sum -= nums[slow++];
                fast--;
                // printf("[sum:%d slow:%d, fast:%d, ans=%d]\n", sum, slow, fast, ans);
            }
        }
        if (ans < 0x7fffffff) return ans;
        else return 0;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)




59.螺旋矩阵II

力扣题目链接

1、一个一个看，走满就换方向

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Solution {
public:
    enum Direction {RIGHT, DOWN, LEFT, UP}d;
    // --是否越界--
    bool isOver(int x, int y, int maxX, int maxY) {
        if (x < 0 || y < 0 || x >= maxX || y >= maxY) return true;
        return false;
    }
    // --转向--
    Direction changeDirection(Direction d) {
        switch (d) {
            case RIGHT: d = DOWN; break;
            case DOWN:  d = LEFT; break;
            case LEFT:  d = UP;   break;
            case UP:    d = RIGHT;break;
        }
        return d;
    }
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int> > ans(n, vector<int>(n, 0)); // n*n，初值为0
        d = RIGHT;
        int x = 0, y = 0;
        for (int i = 1; i <= n * n; i++) {
            // --{延伸}或者{转向 + 暂停一次位置}
            switch (d) {
                case RIGHT:
                    if (!isOver(x, y, n, n) && ans[x][y] == 0) {
                        ans[x][y] = i;
                        y++;
                    }
                    else {
                        d = changeDirection(d);
                        // printf("1(%d,%d,[%d])\n", x, y, d);
                        i--;
                        // --放到正确的位置上--
                        y--; x++;
                    }
                    break;
                case DOWN:
                    if (!isOver(x, y, n, n) && ans[x][y] == 0) {
                        ans[x][y] = i;
                        x++;
                    }
                    else {
                        d = changeDirection(d);
                        // printf("2(%d,%d,[%d])\n", x, y, d);
                        i--;
                        // --放到正确的位置上--
                        x--; y--;
                    }
                    break;
                case LEFT:
                    if (!isOver(x, y, n, n) && ans[x][y] == 0) {
                        ans[x][y] = i;
                        y--;
                    }
                    else {
                        d = changeDirection(d);
                        // printf("3(%d,%d,[%d])\n", x, y, d);
                        i--;
                        // --放到正确的位置上--
                        y++; x--;
                    }
                    break;
                case UP:
                    if (!isOver(x, y, n, n) && ans[x][y] == 0) {
                        ans[x][y] = i;
                        x--;
                    }
                    else {
                        d = changeDirection(d);
                        // printf("4(%d,%d,[%d])\n", x, y, d);
                        i--;
                        // --放到正确的位置上--
                        x++; y++;
                    }
                    break;
            }
        }
        return ans;
    }
};
  • 时间复杂度：O(n^2)

2、分圈，一圈看四条边【代码随想录】




二、链表

203.移除链表元素

力扣题目链接

增加哨兵节点（养成删除内存的习惯）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // --初值为空的情况--
        if (!head)  return nullptr;
        // --增加一个哨兵节点--
        ListNode* head0 = new ListNode;
        head0->next = head;
        ListNode* tmp = head0;
        // --遍历--
        while (tmp) {
            // --删除--
            if (tmp->next && tmp->next->val == val) {
                tmp->next = tmp->next->next;
                continue;   // 不然会跳判
            }
            tmp = tmp->next;
        }
        return head0->next;
    }
};
  • 时间复杂度：O(n)




707.设计链表

力扣题目链接

遇到tmp->next，还是判一下tmp吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class MyLinkedList {
public:
    // --单链表--
    struct ListNode {
        int val;
        ListNode *next;
        ListNode() : val(0), next(nullptr) {}
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode *next) : val(x), next(next) {}
    } *head;
    // --初始化--
    MyLinkedList() {
        // --哨兵节点--
        head = new ListNode;
    }
    // --获取index位置的值，不存在返回-1--
    int get(int index) {
        ListNode *tmp = head->next;
        while (index--) {
            if (!tmp) return -1;
            tmp = tmp->next;
        }
        if (!tmp) return -1;
        return tmp->val;
    }
    // --加到开头--
    void addAtHead(int val) {
        ListNode *newNode = new ListNode(val);
        newNode->next = head->next;
        head->next = newNode;
    }
    // --加到结尾--
    void addAtTail(int val) {
        ListNode *newNode = new ListNode(val);
        ListNode *tmp = head;
        while (tmp->next) tmp = tmp->next;
        tmp->next = newNode;
    }
    // --加到index位置前--
    void addAtIndex(int index, int val) {
        ListNode *newNode = new ListNode(val);
        ListNode *tmp = head;
        while (index-- && tmp) tmp = tmp->next;
        if (index > 0 || !tmp) return;
        newNode->next = tmp->next;
        tmp->next = newNode;
    }
    // --删除index节点--
    void deleteAtIndex(int index) {
        ListNode *tmp = head;
        // --目标为tmp->next
        while (index-- && tmp) tmp = tmp->next;
        if (index > 0 || !tmp || !tmp->next) return;
        ListNode *need2Delete = tmp->next;
        tmp->next = tmp->next->next;
        delete need2Delete;
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */




206.反转链表

力扣题目链接

1、双指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        // --一次记录两个节点--
        ListNode *slow = head;
        ListNode *fast = head->next;
        ListNode *tmp = nullptr;
        // --第一个先指向空--
        slow->next = nullptr;
        while (fast) {
            // --改为：后一个指向前一个--
            tmp = fast->next;
            fast->next = slow;
            slow = fast;
            fast = tmp;
        }
        return slow;
    } 
};
  • 时间复杂度：O(n)

2、递归法




24.两两交换链表中的节点

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;
        // --添加一个哨兵节点--
        // --一次记录三个节点--
        ListNode *head0 = new ListNode(0, head);
        ListNode *pre = head0;
        ListNode *key1 = head, *key2 = head->next;
        while (1) {
            // --改变结构--
            pre->next = key2;
            key1->next = key2->next;
            key2->next = key1;
            // --准备下一次操作--
            pre = key1;
            key1 = key1->next;
            if (!key1) return head0->next;
            key2 = key1->next;
            if (!key2) return head0->next;
        }
    }
};
  • 时间复杂度：O(n)




19.删除链表的倒数第N个节点

力扣题目链接

1、循环两次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    // --计数--
    int count(ListNode* head) {
        int cnt = 0;
        while (head) {
            cnt++;
            head = head->next;
        }
        return cnt;
    }
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // --倒数化为正数--
        n = count(head) - n + 1;
        // --只有一个的话，n也只能为1了--
        if (!head->next) {
            delete head;
            return nullptr;
        }
        // --增加一个哨兵节点--
        ListNode *head0 = new ListNode(0, head);
        ListNode *fast = head0, *slow = nullptr;
        while (n--) {
            slow = fast;
            fast = fast->next;
        }
        slow->next = fast->next;
        delete fast;
        return head0->next;
    }
};
  • 时间复杂度：O(2n)

2、双指针【进阶】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // --增加一个哨兵节点--
        ListNode *head0 = new ListNode(0, head);
        ListNode *fast = head0, *slow = head0;
        // --fast比slow块n个，fast都是有效节点，slow->next是最后要删除的节点--
        // --fast先前进n次--
        while (n--) fast = fast->next;
        // --fast和slow一起前进，知道fast取到最后一个有效节点--
        while (fast->next) {
            fast = fast->next;
            slow = slow->next;
        }
        // --删除slow->next--
        ListNode *need2Delete = slow->next;
        slow->next = slow->next->next;
        delete need2Delete;
        return head0->next;
    }
};
  • 时间复杂度：O(n)




面试题 02.07. 链表相交

力扣题目链接

同：160. 相交链表 - 力扣（Leetcode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    // --计数--
    int count(ListNode *head) {
        int cnt = 0;
        while (head) {
            cnt++;
            head = head->next;
        }
        return cnt;
    }
    // --传入的值nA >= nB--
    ListNode *findAnsNode(int nA, int nB, ListNode *headA, ListNode *headB) {
        // --headA先前进nA - nB个--
        for (int i = 0; i < nA - nB; i++) headA = headA->next;
        if (headA == headB) return headA;
        while (nB--) {
            // --走到最后都没有相等--
            if (!headA->next || !headB->next) return nullptr;
            // --目标是->next--
            if (headA->next == headB->next) return headA->next;
            headA = headA->next;
            headB = headB->next;
        }
        return nullptr;
    }
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int nA = count(headA), nB = count(headB);
        if (nA >= nB) return findAnsNode(nA, nB, headA, headB);
        else return findAnsNode(nB, nA, headB, headA);
    }
};

  • 时间复杂度：O(n + m)

  • 空间复杂度：O(1)




142.环形链表II

力扣题目链接

找到相遇点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 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 *slow = head, *fast = head;
        while (fast && fast->next) {
            // --slow移动一步， fast移动两步--
            slow = slow->next;
            fast = fast->next->next;
            // --相遇了--
            if (slow == fast) {
                // --x：起始点到环入口的距离--
                // --y：环入口到相遇点的距离--
                // --z：相遇点到环入口的距离--
                // --2(x + y) = x + y + n(y + z)-- 
                // --x = n(y + z) - y--
                // --slow从起点开始，fast从相遇点开始--
                slow = head; 
                while (slow != fast) {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        // --出现了终点--
        return nullptr;
    }
};




三、哈希表

242.有效的字母异位词

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isAnagram(string s, string t) {
        vector<int> charSet(26, 0);
        int ns = s.size(), nt = t.size();
        for (int i = 0; i < ns; i++) {
            charSet[s[i] - 'a']++;
        }
        for (int i = 0; i < nt; i++) {
            charSet[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (charSet[i] != 0) return false;
        }
        return true;
    }
};




349.两个数组的交集

力扣题目链接

1、哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> ans;
        unordered_set<int> nums1_set(nums1.begin(), nums1.end());
        for (int item : nums2) {
            // --在nums1中，但是不重复出现--
            if (nums1_set.find(item) != nums1_set.end()) {
                ans.insert(item);	
            }
        }
        return vector<int>(ans.begin(), ans.end());
    }
};

2、数组做哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> ans;
        int record[1000] = {0}; // 初始化为0
        int n1 = nums1.size(), n2 = nums2.size();
        for (int i = 0; i < n1; i++) {
            record[nums1[i]] = 1;
        }
        for (int i = 0; i < n2; i++) {
            if (record[nums2[i]]) ans.insert(nums2[i]);
        }
        return vector<int>(ans.begin(), ans.end());;
    }
};




202.快乐数

力扣题目链接

1、快慢指针 + 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    // --计算位平方和--
    int getSum(int n) {
        int sum = 0;
        while (n) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    // --递归 + 快慢指针求解--
    bool judge(int fast, int slow) {
        // --fast计算两次，slow计算一次--
        fast = getSum(getSum(fast));
        slow = getSum(slow);
        // --重复出现--
        if (fast == 1) return true;
        if (fast == slow) return false;
        return judge(fast, slow);
    }
    bool isHappy(int n) {
        return judge(n, n);
    }
};

2、哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    // --计算位平方和--
    int getSum(int n) {
        int sum = 0;
        while (n) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    bool judge(int n, unordered_set<int>& cnt) {
        if (n == 1) return true;
        if (cnt.find(n) != cnt.end()) {
            return false;
        }
        else {
            cnt.insert(n);
        }
        n = getSum(n);
        return judge(n, cnt);
    }
    bool isHappy(int n) {
        // --哈希表（元素不重复）--
        unordered_set<int> cnt;
        return judge(n, cnt);
    }
};




1.两数之和

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> record;
        // --查找差是否在map中--
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (record.find(target - nums[i]) != record.end()) {
                return {i, record.find(target - nums[i])->second};
            }
            // --不在则记到map中--
            record.insert(pair<int, int>(nums[i], i));
        }
        return {};
    }
};




454.四数相加II

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int ans = 0;
        int n1 = nums1.size(), n2 = nums2.size(), n3 = nums3.size(), n4 = nums4.size();
        unordered_map<int, int> map;
        for (int i : nums1) {
            for (int j : nums2) {
                map[i + j]++;
            }
        }
        for (int k : nums3) {
            for (int l : nums4) {
                // --在map中--
                if (map.find(0 - k - l) != map.end()) {
                    ans += map[0 - k - l];
                }
            }
        }
        return ans;
    }
};




383.赎金信

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        vector<int> mCnt(26, 0);  // 记录杂志字母出现次数
        for (char i : magazine)
            mCnt[i - 'a']++;
        for (char i : ransomNote) {
            mCnt[i - 'a']--;
            // --单词不够了--
            if (mCnt[i - 'a'] < 0) return false;
        }
        return true;
    }
};




15.三数之和

力扣题目链接




18.四数之和

力扣题目链接




四、字符串

344.反转字符串

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
            left++; right--;
        }
    }
};




541.反转字符串II

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    // --修改了344.反转字符串的代码--
    void reverseString(string& s, int left, int right) {
        while (left < right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
            left++; right--;
        }
    }
    string reverseStr(string s, int k) {
        int n = s.size();   // 获取长度
        int begin = 0;      // 第几2k的起止位置
        for (int i = 0; i < n; i += 2 * k) {
            // --判断一下剩余字符--
            int left = n - i;
            if (left < k) {
                reverseString(s, begin, n - 1);
                break;
            }
            else if (left < 2 * k) {
                reverseString(s, begin, begin + k - 1);
                break;
            }
            // --开始翻转--
            reverseString(s, begin, begin + k - 1);
            begin += 2 * k;
        }
        return s;
    }
};




剑指Offer 05.替换空格

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    string replaceSpace(string s) {
        // --计算空格数--
        int oldSize = s.size();
        int cnt = 0;
        for (int i = 0; i < oldSize; i++) {
            if (s[i] == ' ') cnt++;
        }
        // --扩大数组，加上所有空格的大小（本来就占用一个了）--
        s.resize(oldSize + cnt *2);
        int newSize = s.size();
        // --slow遍历，fast指向下一个存放的位置--
        int slow = oldSize - 1, fast = newSize - 1;
        while (slow < fast) {
            if (s[slow] == ' ') {
                s[fast--] = '0';
                s[fast--] = '2';
                s[fast--] = '%';
                slow--;
            }
            else s[fast--] = s[slow--];
        }
        return s;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)




151.翻转字符串里的单词

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    // --修改了344.反转字符串的代码--
    void reverseString(string& s, int left, int right) {
        while (left < right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
            left++; right--;
        }
    }
    // --处理多余空格--
    void processSpaces(string& s) {
        int slow = 0;
        int n = s.size();
        int flag = 0;   // 1；遇到过单词
        for (int fast = 0; fast < n; fast++) {
            if (s[fast] != ' ') {
                flag = 1;
                s[slow++] = s[fast];
            }
            else {
                // --前面有单词，加一个空格--
                if (flag) s[slow++] = ' ';
                flag = 0;
            }
        }
        // --最后有一个空格，或者没有--
        if (s[slow - 1] == ' ') s.resize(slow - 1);
        else s.resize(slow);
    }
    string reverseWords(string s) {
        // --首先将多余空格处理完--
        processSpaces(s);
        // --整体翻转--
        reverseString(s, 0, s.size() - 1);
        // --每个单词进行翻转--
        int begin = 0, end = 0;
        int n = s.size();
        while (end < n) {
            // --区间为[begin, end - 1]--
            if (s[end] == ' ') {
                reverseString(s, begin, end - 1);
                begin = end + 1;
            }
            end++;
        }
        // --最后一个单词没被翻转，加上--
        reverseString(s, begin, end - 1);
        return s;
    }
};




剑指Offer58-II.左旋转字符串

力扣题目链接

不开辟新的空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    // --修改了344.反转字符串的代码--
    void reverseString(string& s, int left, int right) {
        while (left < right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
            left++; right--;
        }
    }
    string reverseLeftWords(string s, int n) {
        // --目的：0 ~ k移动到k + 1 ~ n - 1(这里k = n, n = size)---
        // --先各自翻转，再整体翻转就是答案了--
        reverseString(s, 0, n - 1);
        reverseString(s, n, s.size() - 1);
        reverseString(s, 0, s.size() - 1);
        return s;
    }
};




28.实现 strStr()

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    // --获取模式串s的next数组--
    vector<int> getNext(string s) {
        int n = s.size();
        vector<int> next(n, 0);  // 大小和初值
        int j = -1;
        next[0] = j;
        // --j + 1指向前缀的末尾，i指向后缀的末尾--
        for (int i = 1; i < n; i++) {
            // --不匹配，j回退--
            while (j >= 0 && s[j + 1] != s[i]) {
                j = next[j];
            }
            // --匹配，同时前进--
            if (s[j + 1] == s[i]) j++;
            // --记录next数组--
            next[i] = j;
        }
        return next;
    }
    int strStr(string haystack, string needle) {
        // --对于本题可以不写--
        if (needle.size() == 0) return 0;
        vector<int> next = getNext(needle);
        int n = haystack.size(), m = needle.size();
        int j = -1;
        for (int i = 0; i < n; i++) {
            // --不匹配，j回退--
            while (j >= 0 && needle[j + 1] != haystack[i]) {
                j = next[j];
            }
            // --匹配，前进--
            if (needle[j + 1] == haystack[i]) j++;
            // --完全匹配，结束--
            if (j + 1 == m) {
                return i - needle.size() + 1;
            }
        }
        return -1;
    }
};




459.重复的子字符串

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    // --来自28. 实现 strStr()--
    vector<int> getNext(string s) {
        int n = s.size();
        vector<int> next(n, 0);  // 大小和初值
        int j = -1;
        next[0] = j;
        // --j + 1指向前缀的末尾，i指向后缀的末尾--
        for (int i = 1; i < n; i++) {
            // --不匹配，j回退--
            while (j >= 0 && s[j + 1] != s[i]) {
                j = next[j];
            }
            // --匹配，同时前进--
            if (s[j + 1] == s[i]) j++;
            // --记录next数组--
            next[i] = j;
        }
        return next;
    }
    bool repeatedSubstringPattern(string s) {
        if (s.size() == 0) return false;
        vector<int> next = getNext(s);
        if (next[next.size() - 1] != -1 
        && s.size() % (next.size() - next[next.size() - 1] - 1) == 0)
        return true;
        return false;
    }
};




五、双指针法（同上）

27.移除元素

力扣题目链接




344.反转字符串

力扣题目链接




剑指Offer 05.替换空格

力扣题目链接




151.翻转字符串里的单词

力扣题目链接




206.反转链表

力扣题目链接




24. 两两交换链表中的节点

力扣题目链接




19.删除链表的倒数第N个节点

力扣题目链接




面试题 02.07. 链表相交

力扣题目链接

同：160. 相交链表 - 力扣（Leetcode）




142.环形链表II

力扣题目链接




15.三数之和

力扣题目链接




18.四数之和

力扣题目链接




六、栈与队列

232.用栈实现队列

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class MyQueue {
public:
    // -- 输入栈、输出栈 --
    stack<int> stackIn;
    stack<int> stackOut;
    MyQueue() { }
    void push(int x) {
        stackIn.push(x);
    }
    int pop() {
        // -- 输出栈为空，将输入栈的元素全部取出，放入输出栈 --
        if (stackOut.empty()) {
            while (!stackIn.empty()) {
                stackOut.push(stackIn.top());
                stackIn.pop();
            }
        }
        // -- 输出栈为空，输入栈为空，报错 --
        if (stackOut.empty()) {
            printf("当前没有元素\n");
            return -1;
        }
        // -- 输出栈不为空，直接输出 --
        int res = stackOut.top();
        stackOut.pop();
        return res;
    }
    
    int peek() {
        // --使用了自身的函数，但是pop删除了元素，需要恢复--
        int res = this->pop();
        stackOut.push(res);
        return res;
    }
    
    bool empty() {
        if (stackOut.empty() && stackIn.empty()) return true;
        return false;
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */




225.用队列实现栈

力扣题目链接

1、两个队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class MyStack {
public:
    // --q1作为输入输出栈，q2作为辅助备份栈--
    queue<int> q1;
    queue<int> q2;
    MyStack() {}
    
    void push(int x) {
        q1.push(x);
    }

    int pop() {
        // --q1为空，q2为空，报错--
        if (this->empty()) printf("当前没有元素\n");
        // --q1所有元素放到q2，除了最后一个元素--
        int size = q1.size() - 1;
        while (size--) {
            q2.push(q1.front());
            q1.pop();
        }
        // --最后一个元素就是栈顶--
        int res = q1.front();
        q1.pop();
        // --q1为空，q2不为空，q2变换为q1，q1变换为q2--
        if (q1.empty()) swap(q1, q2);
        return res;
    }
    
    int top() {
         // --使用了自身的函数，但是pop删除了元素，需要恢复--
        int res = this->pop();
        q1.push(res);
        return res;
    }
    
    bool empty() {
        if (q1.empty() && q2.empty()) return true;
        return false;
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

2、一个队列（优化）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class MyStack {
public:
    queue<int> q;
    MyStack() { }
    
    void push(int x) {
        q.push(x);
    }
    
    int pop() {
        // --把前n个重新入队，则最后一个变为第一个，删除即可--
        int res = q.back();
        int t = q.size() - 1;
        while (t--) {
            q.push(q.front());
            q.pop();
        }
        q.pop();
        return res;
    }
    
    int top() {
        // --调用自己的pop，将弹出的添加回去--
        int res = this->pop();
        q.push(res);
        return res;
    }
    
    bool empty() {
        if (q.empty()) return true;
        return false;
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */




20.有效的括号

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        int n = s.size();
        for (int i = 0; i < n; i++ ) {
            // --放入对应的括号，匹配问题变成了相等问题--
            if (s[i] == '(') st.push(')');
            else if (s[i] == '[') st.push(']');
            else if (s[i] == '{') st.push('}');
            else {
                // --1、栈为空--
                if (st.empty()) return false;
                // --2、匹配上--
                else if (st.top() == s[i]) st.pop();
                // --3、不匹配--
                else return false;
            }
        }
        // --4、执行完了，栈不为空--
        return st.empty();
    }
};




1047.删除字符串中的所有相邻重复项

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string removeDuplicates(string s) {
        int slow = 0;   // 指向栈顶的下一个位置
        for (int i = 0; i < s.size(); i++) {
            // --1、栈为空--
            if (slow == 0) {
                s[slow++] = s[i];
            }
            // --2、不相同--
            else if (s[slow - 1] != s[i]) {
                s[slow++] = s[i];
            }
            // --3、相同--
            else {
                slow--;
            }
        }
        s.resize(slow);
        return s;
    }
};




150.逆波兰表达式求值

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    // --转为整数--
    int str2int(const string str) {
        int res = 0;
        int flag = 0; // 1:负数
        for (char i : str) {
            if (i == '-') {
                flag = 1;
                continue;
            }
            res = res * 10 + i - '0';
        }
        return flag ? 0 - res : res;
    }
    int evalRPN(vector<string>& tokens) {
        // --数字栈, 力扣修改了后台测试数据，需要用longlong--
        stack<long long> st;
        for (string i : tokens) {
            // --是数字, 考虑负数--
            if (i[0] >= '0' && i[0] <= '9' || i[0] == '-' && i.size() > 1) {
                st.push(str2int(i));
                printf("%d压入栈\n", str2int(i));
            }
            // --是符号--
            else {
                // --弹出两个操作数，计算--
                int tmp = 0;
                int key2 = st.top();
                st.pop();
                int key1 = st.top();
                st.pop();
                if (i[0] == '+') {
                    tmp = key1 + key2;
                }
                else if (i[0] == '-') {
                    tmp = key1 - key2;
                }
                else if (i[0] == '*') {
                    tmp = key1 * key2;
                }
                else if (i[0] == '/') {
                    tmp = key1 / key2;
                }
                // --压入计算结果--
                st.push(tmp);
                printf("%d %c %d = %d\n", key1, i[0], key2, tmp);
            }
        }
        return st.top();
    }
};




七、二叉树

递归遍历/迭代遍历


144.二叉树的前序遍历

力扣题目链接

1、递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void traverse(TreeNode *node, vector<int>& ans) {
        if (node == nullptr) return;
        ans.push_back(node->val);
        traverse(node->left, ans);
        traverse(node->right, ans);
        return;
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        traverse(root, ans);
        return ans;
    }
};

2、迭代遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode *> st;
        st.push(root);
        while (!st.empty()) {
            TreeNode *tmp = st.top();
            st.pop();
            if (tmp == nullptr) continue;
            ans.push_back(tmp->val);
            st.push(tmp->right);
            st.push(tmp->left);
        }
        return ans;
    }
};




145.二叉树的后序遍历

力扣题目链接

1、递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void traverse(TreeNode *node, vector<int>& ans) {
        if (node == nullptr) return;
        traverse(node->left, ans);
        traverse(node->right, ans);
        ans.push_back(node->val);
        return;
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        traverse(root, ans);
        return ans;
    }
};

2、迭代遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode *> st;
        st.push(root);
        // --修改前序，将顺序变为中右左，最后再翻转就是答案--
        while (!st.empty()) {
            TreeNode *tmp = st.top();
            st.pop();
            if (tmp == nullptr) continue;
            ans.push_back(tmp->val);
            st.push(tmp->left);
            st.push(tmp->right);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};




94.二叉树的中序遍历

力扣题目链接

1、递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void traverse(TreeNode *node, vector<int>& ans) {
        if (node == nullptr) return;
        traverse(node->left, ans);
        ans.push_back(node->val);
        traverse(node->right, ans);
        return;
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        traverse(root, ans);
        return ans;
    }
};

2、迭代遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode *> st;
        while (root || !st.empty()) {
            if (root != nullptr) {
                st.push(root);
                // printf("%d进栈\n", root->val);
                root = root->left;
            }
            else {
                root = st.top();
                ans.push_back(root->val);
                st.pop();
                // printf("%d出栈\n", root->val);
                root = root->right;
            }
        }
        return ans;
    }
};




589.N 叉树的前序遍历

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> ans;
    vector<int> preorder(Node* root) {
        if (root == nullptr) return ans;
        ans.push_back(root->val);   // 前
        for (int i = 0; i < root->children.size(); i++) 
            preorder(root->children[i]);
        return ans;
    }
};




590.N 叉树的后序遍历

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> ans;
    vector<int> postorder(Node* root) {
        if (root == nullptr) return ans;
        for (int i = 0; i < root->children.size(); i++) 
            preorder(root->children[i]);
        ans.push_back(root->val);   // 后
        return ans;
    }
};




层序遍历

102.二叉树的层序遍历

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (!root) return ans;
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty()) {
            int curSize = que.size();  // 当前层有多少个
            vector<int> curAns;     // 记录当前层答案
            for (int i = 0; i < curSize; i++) {
                TreeNode *tmp = que.front();
                curAns.push_back(tmp->val);
                que.pop();
                if (tmp->left) que.push(tmp->left);
                if (tmp->right) que.push(tmp->right);
            }
            ans.push_back(curAns);
        }
        return ans;
    }
};




107.二叉树的层序遍历 II

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        if (!root) return ans;
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty()) {
            int curSize = que.size();  // 当前层有多少个
            vector<int> curAns;     // 记录当前层答案
            for (int i = 0; i < curSize; i++) {
                TreeNode *tmp = que.front();
                curAns.push_back(tmp->val);
                que.pop();
                if (tmp->left) que.push(tmp->left);
                if (tmp->right) que.push(tmp->right);
            }
            ans.push_back(curAns);
        }
        reverse(ans.begin(), ans.end());    // 翻转就行了
        return ans;
    }
};




199. 二叉树的右视图

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        if (root == nullptr) return ans;
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty()) {
            int n = que.size() - 1;
            // --把每一层的最后一个记录下来后弹出，其他弹出即可--
            while (n--) {
                if (que.front()->left) que.push(que.front()->left);
                if (que.front()->right) que.push(que.front()->right);
                que.pop();
            }
            if (que.front()->left) que.push(que.front()->left);
            if (que.front()->right) que.push(que.front()->right);
            ans.push_back(que.front()->val);
            que.pop();
        }
        return ans;
    }
};




637.二叉树的层平均值

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> ans;
        if (!root) return ans;
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty()) {
            double curSum = 0; // 当前层数的和
            int size = que.size();
            for (int i = 0; i < size; i++) {
                curSum += que.front()->val;
                if (que.front()->left) que.push(que.front()->left);
                if (que.front()->right) que.push(que.front()->right);
                que.pop();
            }
            ans.push_back(curSum / size);   // 写入平均值
        }
        return ans;
    }
};




429.N叉树的层序遍历

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ans;
        if (!root) return ans;
        queue<Node *> que;
        que.push(root);
        while (!que.empty()) {
            int curSize = que.size();  // 当前层有多少个
            vector<int> curAns;     // 记录当前层答案
            for (int i = 0; i < curSize; i++) {
                Node *tmp = que.front();
                curAns.push_back(tmp->val);
                que.pop();
                // --压入孩子节点--
                for (Node* j : tmp->children) 
                    if (j) que.push(j);
            }
            ans.push_back(curAns);
        }
        return ans;
    }
};




515.在每个树行中找最大值

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> ans;
        if (!root) return ans;
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty()) {
            int curMax = INT_MIN; // 当前层的最大值
            int size = que.size();
            for (int i = 0; i < size; i++) {
                curMax = curMax < que.front()->val ? que.front()->val : curMax;
                if (que.front()->left) que.push(que.front()->left);
                if (que.front()->right) que.push(que.front()->right);
                que.pop();
            }
            ans.push_back(curMax);   // 写入答案
        }
        return ans;
    }
};




116.填充每个节点的下一个右侧节点指针

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return root;
        queue<Node *> que;
        que.push(root);
        while (!que.empty()) {
            int curSize = que.size();  // 当前层有多少个
            for (int i = 0; i < curSize; i++) {
                Node *tmp = que.front();
                que.pop();
                // --如果是最后一个--
                if (i == curSize - 1) tmp->next = nullptr;
                else tmp->next = que.front();
                if (tmp->left) que.push(tmp->left);
                if (tmp->right) que.push(tmp->right);
            }
        }
        return root;
    }
};




117.填充每个节点的下一个右侧节点指针II

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return root;
        queue<Node *> que;
        que.push(root);
        while (!que.empty()) {
            int curSize = que.size();  // 当前层有多少个
            for (int i = 0; i < curSize; i++) {
                Node *tmp = que.front();
                que.pop();
                // --如果是最后一个--
                if (i == curSize - 1) tmp->next = nullptr;
                else tmp->next = que.front();
                if (tmp->left) que.push(tmp->left);
                if (tmp->right) que.push(tmp->right);
            }
        }
        return root;
    }
};




104.二叉树的最大深度

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        int ans = 0;
        if (!root) return ans;
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty()) {
            ans++;
            int curSize = que.size();  // 当前层有多少个
            for (int i = 0; i < curSize; i++) {
                if (que.front()->left) que.push(que.front()->left);
                if (que.front()->right) que.push(que.front()->right);
                que.pop();
            }
        }
        return ans;
    }
};




111.二叉树的最小深度

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        int ans = 0;
        if (!root) return ans;
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty()) {
            int curSize = que.size();  // 当前层有多少个
            ans++;
            for (int i = 0; i < curSize; i++) {
                // --是否是叶子节点，是的话后面都没必要执行了--
                if (!que.front()->left && !que.front()->right) return ans;
                if (que.front()->left) que.push(que.front()->left);
                if (que.front()->right) que.push(que.front()->right);
                que.pop();
            }
        }
        return ans;
    }
};




226.翻转二叉树

力扣题目链接

1、递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) return root;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

2、迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) return root;
        stack<TreeNode*> st;
        st.push(root);
        while (!st.empty()) {
            TreeNode *tmp = st.top();
            swap(tmp->left, tmp->right);
            st.pop();
            if (tmp->right) st.push(tmp->right);
            if (tmp->left) st.push(tmp->left);
        }
        return root;
    }
};




100.相同的树

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // --1. 子树都为空--
        if (!p && !q) return true;
        // --2. 子树有一个不为空--
        if (p && !q || !p && q) return false;
        // --3. 子树都不为空--
        if (p->val == q->val      // 自己是否相等
            && isSameTree(p->left, q->left)  // p左子树和q左子树是否相等
            && isSameTree(p->right, q->right))  // p右子树和q右子树是否相等
            return true;
        return false;
    }
};




101.对称二叉树

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool preOrdertraverse(TreeNode *t1, TreeNode *t2) {
        // --1. 子树都为空--
        if (!t1 && !t2) return true;
        // --2. 子树有一个不为空--
        if (t1 && !t2 || !t1 && t2) return false;
        // --3. 子树都不为空--
        if (t1->val == t2->val      // 自己是否相等
            && preOrdertraverse(t1->left, t2->right)  // t1左子树和t2右子树是否相等
            && preOrdertraverse(t1->right, t2->left))  // t1右子树和t2左子树是否相等
            return true;
        return false;
    }
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return preOrdertraverse(root->left, root->right);
    }
};




572.另一棵树的子树

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // --来自 100.相同的树 --
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // --1. 子树都为空--
        if (!p && !q) return true;
        // --2. 子树有一个不为空--
        if (p && !q || !p && q) return false;
        // --3. 子树都不为空--
        if (p->val == q->val      // 自己是否相等
            && isSameTree(p->left, q->left)  // p左子树和q左子树是否相等
            && isSameTree(p->right, q->right))  // p右子树和q右子树是否相等
            return true;
        return false;
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (!root) return false;
        return isSameTree(root, subRoot) 
            || isSubtree(root->left, subRoot) 
            || isSubtree(root->right, subRoot);
    }
};




559.n叉树的最大深度

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    int maxDepth(Node* root) {
        int ans = 0;
        if (!root) return ans;
        queue<Node *> que;
        que.push(root);
        while (!que.empty()) {
            ans++;
            int curSize = que.size();  // 当前层有多少个
            for (int i = 0; i < curSize; i++) {
                for (Node* j : que.front()->children)
                    if (j) que.push(j);
                que.pop();
            }
        }
        return ans;
    }
};




222.完全二叉树的节点个数

力扣题目链接

1、当做普通二叉树遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        int ans = 0;
        if (!root) return ans;
        stack<TreeNode*> st;
        st.push(root);
        while (!st.empty()) {
            ans++;
            TreeNode *tmp = st.top();   // 中
            st.pop();
            if (tmp->right) st.push(tmp->right);    // 右
            if (tmp->left) st.push(tmp->left);      // 左
        }
        return ans;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

2、完全二叉树

完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        if (!root) return 0;
        TreeNode *left = root->left;
        TreeNode *right = root->right;
        int lenLeft = 0, lenRight = 0;
        // --统计左边深度--
        while (left) {
            lenLeft++;
            left = left->left;
        }
        // --统计右边深度--
        while (left) {
            lenRight++;
            right = right->right;
        }
        // --左边深度 等于 右边深度，说明这里完全二叉树是满二叉树--
        if (lenLeft == lenRight) return (2 << lenLeft) - 1;   // 右移相当于*2
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};
  • 时间复杂度：O(log n × log n)
  • 空间复杂度：O(log n)




110.平衡二叉树

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // --返回深度--
    int postOrderTravese(TreeNode *t, int depth) {
        if (!t) return depth - 1;
        int lenLeft = postOrderTravese(t->left, depth + 1);
        int lenRight = postOrderTravese(t->right, depth + 1);
        return abs(lenLeft - lenRight) > 1 ? -1 : max(lenLeft, lenRight);
    }
    bool isBalanced(TreeNode* root) {
        if (!root) return true;
        if (postOrderTravese(root, 1) == -1) return false;
        return true;
    }   
};




257. 二叉树的所有路径

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void postOrderTraverse(TreeNode *t, string s, vector<string>& ans) {
        // --是叶子节点--
        if (!t->left && !t->right) ans.push_back(s);
        else {
            // --左子树不为空--
            if (t->left) postOrderTraverse(t->left, s + "->" + to_string(t->left->val), ans);
            // --右子树不为空--
            if (t->right) postOrderTraverse(t->right, s + "->" + to_string(t->right->val), ans);
        }
        return;
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans;
        if (!root) return ans;
        postOrderTraverse(root, to_string(root->val), ans);
        return ans;
    }
};




404.左叶子之和

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (!root) return 0;
        int ans = 0;
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            while (size--) {
                if (que.front()->left) {
                    que.push(que.front()->left);
                    // --是左子树，判断是否是叶子结点--
                    if (!que.front()->left->left && !que.front()->left->right)
                        ans += que.front()->left->val;
                }
                if (que.front()->right) que.push(que.front()->right);
                que.pop();
            }
        }
        return ans;
    }
};




513.找树左下角的值

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        if (!root) return 0;
        int ans = 0;
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            // --更新为这一层的第一个即可--
            ans = que.front()->val;
            while (size--) {
                if (que.front()->left) que.push(que.front()->left);
                if (que.front()->right) que.push(que.front()->right);
                que.pop();
            }
        }
        return ans;
    }
};




112.路径总和

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool traverse(TreeNode *t, int targetSum, int curSum) {
        if (!t) return false;
        curSum += t->val;
        // --是叶子节点并且，curSum 为目标值
        if (curSum == targetSum && !t->left && !t->right)
            return true;
        return traverse(t->left, targetSum, curSum) 
            || traverse(t->right, targetSum, curSum);
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        return traverse(root, targetSum, 0);
    }
};




106.从中序与后序遍历序列构造二叉树

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // --返回key的索引--
    int findRoot (vector<int>& inorder, int key, int inbegin, int inend) {
        for (int i = inbegin; i <= inend; i++) {
            if (inorder[i] == key) return i;
        }
        return -1;
    }
    TreeNode* preOrder(vector<int>& inorder, int inbegin, int inend, 
                vector<int>& postorder, int postbegin, int postend) {
        // printf("[%d, %d], [%d, %d]\n", inbegin, inend, postbegin, postend);
        // --没有节点了--
        if (inbegin > inend) return nullptr; 
        // --在中根序中找到根节点--
        int inRoot = findRoot(inorder, postorder[postend], inbegin, inend);
        // --构造节点，改变区间接着递归--
        return new TreeNode(postorder[postend], // 根
        preOrder(inorder, inbegin, inRoot - 1, postorder, postbegin, postbegin + (inRoot - 1 - inbegin)),    // 左子树
        preOrder(inorder, inRoot + 1, inend, postorder, postend - 1 - (inend - inRoot - 1) ,postend - 1));   // 右子树
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return preOrder(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
    }
};




654.最大二叉树

力扣题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // --返回最大值的索引--
    int findRoot (vector<int>& nums, int begin, int end) {
        int maxVal = INT_MIN, index = -1;
        for (int i = begin; i <= end; i++) 
            if (maxVal < nums[i]) {
                maxVal = nums[i];
                index = i;
            }
        return index;
    }
    TreeNode* construct(vector<int>& nums, int begin, int end) {
        if (begin > end) return nullptr;
        int indexRoot = findRoot(nums, begin, end);
        return new TreeNode(nums[indexRoot],    // 根
        construct(nums, begin, indexRoot - 1),  // 左子树
        construct(nums, indexRoot + 1, end));   // 右子树
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return construct(nums, 0, nums.size() - 1);
    }
};




617.合并二叉树

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        // --1、两个都为空--
        if (!root1 && !root2) return nullptr;
        // --2、有一个为空--
        if (!root1 && root2) return root2;
        if (root1 && !root2) return root1;
        // --3、都不为空--
        root1->val += root2->val;
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        return root1;
    }
};




700.二叉搜索树中的搜索

力扣题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (!root) return nullptr;
        // --本节点是--
        if (root->val == val) return root;
        // 递归
        TreeNode *left = searchBST(root->left, val);
        if (left) return left;
        return searchBST(root->right, val);
    }
};




98.验证二叉搜索树

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void inorder(TreeNode* t, vector<int>& res) {
        if (!t) return;
        inorder(t->left, res);
        res.push_back(t->val);
        inorder(t->right, res);
        return;
    }
    bool isValidBST(TreeNode* root) {
        // --将中根序放入数组中，检查是否有序即可--
        vector<int> res;
        inorder(root, res);
        for (int i = 1; i < res.size(); i++) 
            if (res[i - 1] >= res[i]) return false;
        return true;
    }
};




530.二叉搜索树的最小绝对差

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void inorder(TreeNode* t, vector<int>& res) {
        if (!t) return;
        inorder(t->left, res);
        res.push_back(t->val);
        inorder(t->right, res);
        return;
    }
    int getMinimumDifference(TreeNode* root) {
        // --将中根序放入数组中，计算最小差值即可--
        vector<int> res;
        inorder(root, res);
        int minDiff = INT_MAX;
        for (int i = 1; i < res.size(); i++) {
            int tmp = res[i] - res[i - 1];
            minDiff = minDiff > tmp ? tmp : minDiff;
        }
        return minDiff;
    }
};




501.二叉搜索树中的众数

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> majority; // 记录当前找到的众数
    int curMSize = 0;     // 记录当前找到的众数,它有多少个
    int cnt = 0;          // 记录当前重复元素
    int pre = INT_MIN;    // 上一个元素
    void inOrderTraverse(TreeNode* root) {
        if (!root) return;
        inOrderTraverse(root->left);
        // --与上一个元素相同，意味着重复了--
        if (pre == root->val) cnt++;
        else cnt = 1;
        pre = root->val;
        printf("%d %d\n", curMSize, cnt);
        if (curMSize == cnt) majority.push_back(root->val);
        else if (curMSize < cnt) {
            // --将所有元素清空，将这个众数放入--
            vector<int>().swap(majority);
            majority.push_back(root->val);
            curMSize = cnt;
        }
        inOrderTraverse(root->right);
    }
    vector<int> findMode(TreeNode* root) {
        inOrderTraverse(root);
        return majority;
    }
};




236. 二叉树的最近公共祖先

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == p || root == q || root == NULL) return root;
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if (left && !right) return left;
        if (!left && right) return right;
        if (left && right) return root;
        return nullptr;
    }
};




701.二叉搜索树中的插入操作

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root) return root = new TreeNode(val);
        // --看左子树--
        if (val < root->val) {
            if (!root->left)
                root->left = new TreeNode(val);
            else insertIntoBST(root->left, val);
        }
        // --看右子树--
        if (val > root->val) {
            if (!root->right) 
                root->right = new TreeNode(val);
            else insertIntoBST(root->right, val);
        }
        return root;
    }
};




450.删除二叉搜索树中的节点

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return root;
        // --找到要删除的节点--
        if (root->val == key) {
            TreeNode *need2delete = root;
            // --1、左右孩子都为空--
            if (!root->left && !root->right) root = nullptr;
            // --2、左孩子为空--
            else if (!root->left && root->right) root = root->right;
            // --3、右孩子为空--
            else if (root->left && !root->right) root = root->left;
            // --4、左右孩子都不为空--
            else if (root->left && root->right) {
                // --左子树放到右子树的左下角叶节点的左孩子上--
                TreeNode *tmp = root->right;
                while (tmp->left) tmp = tmp->left;
                tmp->left = root->left;
                root = root->right;
            }
            delete need2delete;
        }
        // --没找到--
        else {
            if (root->val > key) root->left = deleteNode(root->left, key);
            if (root->val < key) root->right = deleteNode(root->right, key);
        }
        return root;
    }
};




八、图论

797.所有可能的路径

797. 所有可能的路径 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    // -- 表结点 -- 
    struct ArcNode {
        int adjvex;     // 邻接顶点
        ArcNode *nextarc;
        ArcNode() : adjvex(0), nextarc(NULL) {}
    }; 
    // -- 头结点 --
    struct VNode {
        ArcNode *nextarc;
        VNode() : nextarc(NULL) {}
    };
    // -- 深搜 --
    vector<vector<int>> ans;
    void dfs(vector<int> &path, vector<VNode> vnode, int begin, int target) {
        for (ArcNode *p = vnode[begin].nextarc; p; p = p->nextarc) {
            path.push_back(p->adjvex);
            if (p->adjvex == target) {  // 找到了
                vector<int> copypath;
                copypath.assign(path.begin(), path.end());
                ans.push_back(copypath);
                path.pop_back();        // 回退
                continue;               // 这条路没必要往下了
            }
            dfs(path, vnode, p->adjvex, target);    // 一直往下
            path.pop_back();            // 回退
        }
    }
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<VNode> vnode(graph.size());
        // -- 构造邻接表 --
        for (int i = 0; i < graph.size(); i++) {
            for (int k : graph[i]) {
                ArcNode *tmp = new(ArcNode);
                tmp->adjvex = k;
                tmp->nextarc = vnode[i].nextarc;
                vnode[i].nextarc = tmp;
            }
        }
        vector<int> path;
        path.push_back(0);  // 第一个位置是0
        dfs(path, vnode, 0, graph.size()-1);
        return ans;
    }
};




200. 岛屿数量

200. 岛屿数量 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    int directionX[4] = {-1, 0, 1, 0};
    int directionY[4] = {0, -1, 0, 1};
    // 赋值并检查越界情况
    bool check (int &i, int &j, int x, int y, int m, int n) {
        int tmpi = i + x, tmpj = j + y;
        if (tmpi <= -1 || tmpj <= -1 
        ||  tmpi >= m || tmpj >= n) return false;   // 越界
        i = tmpi;
        j = tmpj;
        return true;
    }
    // -- 从i, j开始 --
    void dfs(vector<vector<char>> &grid, vector<vector<int>>& visited, int i, int j, int m, int n) {
        visited[i][j] = 1;      // 标记已经访问
        for (int k = 0; k < 4; k++) {
            int x = directionX[k];
            int y = directionY[k];
            int tmpi = i, tmpj = j;
            if (check(tmpi, tmpj, x, y, m, n) == false) continue;    // 越界跳过
            if (visited[tmpi][tmpj] == 0 && grid[tmpi][tmpj] == '1') {// 再在附近找一个可以过去的点，但是没去过的点
                dfs(grid,visited , tmpi, tmpj, m, n);
            }
        } 
    }
    int numIslands(vector<vector<char>>& grid) {
        // -- 用类似找连通分量的方法 --
        int ans = 0;
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> visited(m, vector<int>(n, 0));    // 标记结点是否访问过
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n ; j++) {
                if (visited[i][j] == 0 && grid[i][j] == '1') {
                    ans++;  // 一次dfs一个岛屿
                    dfs(grid, visited, i, j, m, n);
                }
            } 
        }
        return ans;
    }
};