题干分析:题目要求我们针对一个只有两个节点发生错误互换的二叉搜索树进行修复.二叉搜索树定义如下：节点的左子树只包含 严格小于 当前节点的数。节点的右子树只包含 严格大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。针对二叉搜索树,其中序遍历序列应为一个严格递增序列.依题意得,这个二叉搜索树有且仅有两个节点发生了互换,因此中序遍历序列应当也只有两个序列值不符合严格递增规定.算法思路:我们只需针对两个不符合严格递增节点进行值互换即可,但注意这两个节点是否相邻有两种情况:情况1:不相邻: 例如中序序列为 1, 8, 3, 4, 5, 6, 7, 2, 9,其中2与8发生了互换,中序遍历时...

题干解析:检验一棵树是否为二叉树,检验成功则返回true,不成功则为false有效 二叉搜索树定义如下：节点的左子树只包含 严格小于 当前节点的数。节点的右子树只包含 严格大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。针对二叉树搜索树有一个众所周知的结论(不知道的现在就知道了):对二叉搜索树进行中序遍历得到的节点值数组为严格递增数组.应用此结论,题目就变成了中序遍历此树,遍历的同时判断序列是否严格递增算法思路:递归中序遍历,每次与前一个节点最大值进行比较,如果大于则继续递归,小于则结束递归,返回false实现代码: /** * Definition for a binary t...

题目链接:洛谷P2168题干解析:总体需求: 题目要求我们针对n种不同的单词,使用k进制编码进行编号,使编码后的文本长度最小.对于任意两个不同的单词,其编码不能有公共前缀.追加需求: 在确保总长最小的情况下使最长编码尽可能最短.这是典型的哈夫曼编码压缩的实现,同时需要我们建立的哈夫曼树高度尽可能小.此后此题基本上没有其他限制,模拟实现即可.算法思路:由于题目允许k进制编码,传统的二叉哈夫曼树并不完全契合本题情况,以下实现通过模拟k叉树进行实现.首先建立哈夫曼树过程:由于k叉哈夫曼树子叶节点数m应满足: (m - 1) mod (k - 1) = 0,即(m - 1)能被k - 1整除(建立的k...

/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ ListNode* deleteDuplicates(ListNode* head) { // write code here if (...

/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ ListNode* reverseKGroup(ListNode* head, int k) { //...

/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ #include <bits/types/struct_tm.h> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNod...

/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ #include <set> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param lists ListNode类vector * @return ListNode类 */ ListNode* mergeKLists(vector<ListNode...

#include <climits> #include <deque> #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param num int整型vector * @param size int整型 * @return int整型vector */ vector<int> maxInWindows(vector<int>& num, int size) { // write code h...

class Solution { public: void push(int node) { while (!stack2.empty()) { stack1.push(stack2.top()); stack2.pop(); } stack1.push(node); } int pop() { while (!stack1.empty()) { stack2.push(stack1.top()); stack1.pop(); } int data = stack2.top(); stack2.pop(); return data; } private: stack<int> st...