LCR 176. 判断是否为平衡二叉树
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
示例 1：
**输入：**root = [3,9,20,null,null,15,7]
**输出：**true
**解释：**如下图
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
解释：如下图
提示：
0 <= 树的结点个数 <= 10000
首先想到分别计算左右子树深度，再比较，之后再分别判断左右子树
在计算树深度的过程中，我们其实已经计算过所有左右子树深度了（max(left,right)）
所以在取max前我们可以直接判断相差是否大于一，如果大于一则可以直接一路返回
1234567891011121314151617181920class Solution {public: bool isBalanced(TreeNode *root) { return depth(root) != -1; } int depth(TreeNode *ro ...
LCR 175. 计算二叉树的深度
某公司架构以二叉树形式记录，请返回该公司的层级数。
示例 1：
**输入：**root = [1, 2, 2, 3, null, null, 5, 4, null, null, 4]
输出: 4
解释: 上面示例中的二叉树的最大深度是 4，沿着路径 1 -> 2 -> 3 -> 4 或 1 -> 2 -> 5 -> 4 到达叶节点的最长路径上有 4 个节点。
提示：
节点总数 <= 10000
求二叉树的深度，即max(左子树深度，右子树深度)+1
或者直接递归遍历，每次到叶子结点时更新最大深度
123456789class Solution {public: int calculateDepth(TreeNode *root) { if (root == nullptr) return 0; return max(calculateDepth(root->left), calculateDepth(root->right)) + 1; } ...
LCR 174. 寻找二叉搜索树中的目标节点
某公司组织架构以二叉搜索树形式记录，节点值为处于该职位的员工编号。请返回第 cnt 大的员工编号。
示例 1：
**输入：**root = [7, 3, 9, 1, 5], cnt = 2
7
/ \
3 9
/ \
1 5
**输出：**7
示例 2：
输入: root = [10, 5, 15, 2, 7, null, 20, 1, null, 6, 8], cnt = 4
10
/ \
5 15
/ \ \
2 7 20
/ / \
1 6 8
输出: 8
提示：
1 ≤ cnt ≤ 二叉搜索树元素个数
二叉搜索树中序遍历，按左子树，根节点，右子树是从小到大
先右子树即可
123456789101112131415class Solution {public: vector<int> m; int findTargetNode(TreeNode *root, int cnt) { findCnt(root, cnt); return m[cnt - 1]; } void findCn ...
LCR 173. 点名
某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。
示例 1：
**输入：**records = [0,1,2,3,5]
**输出：**4
示例 2：
**输入：**records = [0, 1, 2, 3, 4, 5, 6, 8]
**输出：**7
提示：
1 <= records.length <= 10000
二分查找，因为不缺席的话有 i=records[i]，符合条件则说明缺席人员所在区间为右边
123456789101112131415class Solution {public: int takeAttendance(vector<int> &records) { int l = 0; int r = records.size(); while (l < r) { int mid = l + (r - l) / 2; if (mid == r ...
LCR 172. 统计目标成绩的出现次数
某班级考试成绩按非严格递增顺序记录于整数数组 scores，请返回目标成绩 target 的出现次数。
示例 1：
输入: scores = [2, 2, 3, 4, 4, 4, 5, 6, 6, 8], target = 4
输出: 3
示例 2：
输入: scores = [1, 2, 3, 5, 7, 9], target = 6
输出: 0
提示：
0 <= scores.length <= 10(5)
-10(9) <= scores[i] <= 10(9)
scores 是一个非递减数组
-10(9) <= target <= 10(9)
有序数组，二分查找第一个大于等于target的索引，和第一个大于target的索引，相减即可
12345678class Solution {public: int countTarget(vector<int> &scores, int target) { auto l = lower_bound(scores.begin(), scores ...
LCR 171. 训练计划 V
某教练同时带教两位学员，分别以链表 l1、l2 记录了两套核心肌群训练计划，节点值为训练项目编号。两套计划仅有前半部分热身项目不同，后续正式训练项目相同。请设计一个程序找出并返回第一个正式训练项目编号。如果两个链表不存在相交节点，返回 null 。
此题是寻找链表公共结点，设公共部分长c，单独的部分分别为a，b
首先想到的是先同时遍历两个链表，当短的一方遍历结束时（共a+c），另一方也遍历了（a+c），另一方还需要遍历（b-a），而从头遍历的话A需要遍历a，B需要遍历b
再次从头遍历B，当b-a遍历结束时，还需遍历（a）即可到达公共结点，此距离与从头遍历A的距离相等，
所以此时同时开始遍历A，两节点在遍历过程中一定会相交
123456789101112131415161718192021222324252627282930313233class Solution {public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (headA == NULL ...
