236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
**输入：**root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
**输出：**3
**解释：**节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
**输入：**root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
**输出：**5
**解释：**节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
**输入：**root = [1,2], p = 1, q = 2
**输出：**1
提示：
树中节点数目在范围 [2, 10(5)] 内。
-10(9) <= Node.val <= 10(9)
所有 Node.val 互不相同 。
p != q
p 和 ...
234. 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
**输入：**head = [1,2,2,1]
**输出：**true
示例 2：
**输入：**head = [1,2]
**输出：**false
提示：
链表中节点数目在范围[1, 10(5)] 内
0 <= Node.val <= 9
**进阶：**你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
首先可以想到用快慢指针找到链表中间节点
对于奇数个节点为中间，对于偶数个节点为后半部分的起始节点
想要一边遍历一边比较，我们可以反转后半部分链表，这样就可以从尾开始遍历了
123456789101112131415161718192021222324252627282930class Solution {public: bool isPalindrome(ListNode *head) { ListNode *h = head; ListNode *mid = head; ...
230. 二叉搜索树中第 K 小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）。
示例 1：
**输入：**root = [3,1,4,null,2], k = 1
**输出：**1
示例 2：
**输入：**root = [5,3,6,2,4,null,null,1], k = 3
**输出：**3
提示：
树中的节点数为 n 。
1 <= k <= n <= 10(4)
0 <= Node.val <= 10(4)
**进阶：**如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
首先想到中序遍历，遍历结果是有序的
只需要记录当前遍历了多少个元素即可，当cur==k可以返回
1234567891011121314151617181920212223class Solution {public: int ans = 0; bool flag = false; int kthSmallest(TreeNode *root, int k) ...
226. 翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
**输入：**root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
**输入：**root = [2,1,3]
输出：[2,3,1]
示例 3：
**输入：**root = []
输出：[]
提示：
树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100
递归翻转
先交换左右子树，再递归翻转左右子树
或者先翻转左右子树，再交换
12345678910111213class Solution {public: TreeNode *invertTree(TreeNode *root) { if (root == nullptr) return root; TreeNode *l = root->left; root->left = root->right; root->right = l; ...
215. 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示：
1 <= k <= nums.length <= 10(5)
-10(4) <= nums[i] <= 10(4)
首先想到使用小顶堆维护k个元素，处理完整个数组后堆顶即为所求
12345678910111213141516class Solution {public: int findKthLargest(vector<int> &nums, int k) { priority_queue<int, vector<int>, greater<int>> pq; for ...
208. 实现 Trie (前缀树)
Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
示例：
输入
[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
[[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
输出
[null, null, true, false, tr ...
