LC-110-平衡二叉树
https://leetcode.cn/problems/balanced-binary-tree/
题面给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
返回 false 。
代码（递归）12345678910111213// 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了就返回-1int getHeight(TreeNode* node) { if (node == NULL) return 0; int leftHeight = getHeight(node->left); if (leftHeight == -1) return -1; int rightHeight = getHeight(node->right); if (rightHeigh ...
LC-111-二叉树的最小深度
https://leetcode.cn/problems/minimum-depth-of-binary-tree/
题面给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
返回它的最小深度 2。
思路这道题和求最大深度差别比较大的。
依然是前序后序遍历均可，前序求的是深度，后续求的是高度。
好好审题：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意，是叶子节点。
递归写法后序12345678910111213141516int getDepth(TreeNode* node) { if (node == NULL) return 0; int leftDepth = getDepth(node->left); // 左 int rightDepth = getDepth(node->right); // 右 ...
LC-104-二叉树的最大深度
https://leetcode.cn/problems/maximum-depth-of-binary-tree/
题面给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
12输入：root = [3,9,20,null,null,15,7]输出：3
示例 2：
12输入：root = [1,null,2]输出：2
提示：
树中节点的数量在 [0, 104] 区间内。
-100 <= Node.val <= 100
代码递归写法12345678910int getdepth(TreeNode* node) { if (node == NULL) return 0; int leftdepth = getdepth(node->left); int rightdepth = getdepth(node->right); int depth = 1 + max(leftdepth, rightdepth); return depth; ...
LC-101-对称二叉树
https://leetcode.cn/problems/symmetric-tree/
题面给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
12输入：root = [1,2,2,3,4,4,3]输出：true
示例 2：
12输入：root = [1,2,2,null,3,null,3]输出：false
提示：
树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100
进阶：你可以运用递归和迭代两种方法解决这个问题吗？
思路递归123456789101112131415161718bool compare(TreeNode* left, TreeNode* right) { // 首先排除空节点的情况 if (left == NULL && right != NULL) return false; else if (left != NULL && right == NULL) return false; else if (left == N ...
LC-226-翻转二叉树
https://leetcode.cn/problems/invert-binary-tree/
题面给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
12输入：root = [4,2,7,1,3,6,9]输出：[4,7,2,9,6,3,1]
示例 2：
12输入：root = [2,1,3]输出：[2,3,1]
示例 3：
12输入：root = []输出：[]
提示：
树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100
代码递归写法1234567TreeNode* invertTree(TreeNode* root) { if (root == NULL) return root; swap(root->left, root->right); // 中 invertTree(root->left); // 左 invertTree(root->right); // 右 return root;&# ...
LC-102-二叉树的层序遍历
二叉树层序遍历模板迭代写法12345678910111213141516171819vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; queue<TreeNode*> que; if (root != NULL) que.push(root); while (!que.empty()) { int size = que.size(); vector<int> vec; // 这里一定要使用固定大小size，不要使用que.size()，因为que.size()是不断变化的 for (int i = 0; i < size; i++) { TreeNode* node = que.front(); que.pop(); vec.push ...
二叉树的节点定义和遍历方式
## 二叉树节点的定义模板C++
123456struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x): val(x), left(NULL), right(NULL) {}}
Java
12345678910111213public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }} ...
LC-347-前K个高频元素
题面给定一个非空的整数数组，返回其中出现频率前 k 高的元素。（力扣后来加了一句：你可以按 任意顺序 返回答案。我们先假设没有这句。）
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 $O(n \log n)$ , n 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。
思路 小顶堆，时间O(n log k)，空间O(n)C++
123456789101112131415161718192021222324252627282930313233public: // 小顶堆 class mycomparison { public: bool operator() (const pair<int, int> ...
LC-239-滑动窗口最大值
https://leetcode.cn/problems/sliding-window-maximum/
题面给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
进阶：
你能在线性时间复杂度内解决此题吗？
提示：
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length
思路① 单调队列，时间O(n)，空间O(k)C++
123456789101112131415161718192021222324252627282930313233343536private: class MyQueue { // 单调队列（从大到小） public: Deque<int> que; // 用deque来实现单调队列 // 每次弹出的 ...
LC-150-逆波兰表达式求值
https://leetcode.cn/problems/evaluate-reverse-polish-notation/
题面根据 逆波兰表示法，求表达式的值。
有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入: [“2”, “1”, “+”, “3”, “ * “]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入: [“4”, “13”, “5”, “/“, “+”]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入: [“10”, “6”, “9”, “3”, “+”, “-11”, “ * “, “/“, “ * “, “17”, “+”, “5”, “+”]
输出: 22
解释:该算式转化 ...