比亚迪
近日，车企巨头比亚迪的内部信被曝光。
内部信内容是关于员工待遇的，信中反复强调：比亚迪始终坚持为每一位员工提供公平合理的工作环节和回报机制，鼓励员工工作中展现努力施展自己的才华和价值，来获得更为丰厚的回报，这里没有大锅饭，只有公平的薪酬和晋升制度。
在结合此前在 xhs 看到的 BYD 待遇爆料。
若基本属实的话，在普遍裁员的如今，迪子的待遇还是可以的。
工资加月度绩效，基本上可以确保每个月的工资为 140% ~ 150%，同时上半年和下半年均有一次升职加薪机会，而年终绩效基本上 80% 的人都有，基本水平在 2~3 个月工资，然后大概 2~3 年会有一次额外的股票激励。
前有「原新能源势力领跑者」理想汽车宣布裁员 18% 后又魔幻召回被裁员工，后有 BYD 最新待遇曝光，什么格调都是假的，只有销量和生意才是真的。
...
回归主线。
端午假日的尾巴，来一道稍微简单，和「比亚迪」相关的算法原题。
题目描述
平台：LeetCode
题号：998
最大树定义：一棵树，并满足「其中每个节点的值都大于其子树中的任何其他值」。
给你最大树的根节点 root 和一个整数 val 。
给定的树是利用 Construct(a) 例程从列表 a（root = Construct(a)）递归地构建的：
-
如果 a为空，返回null -
否则，令 a[i]作为a的最大元素。创建一个值为a[i]的根节点root -
root的左子树将被构建为Construct([a[0],a[1],...,a[i - 1]]) -
root的右子树将被构建为Construct([a[i+1],a[i+2],...,a[a.length-1]]) -
返回 root
请注意，题目没有直接给出 a，只是给出一个根节点 root = Construct(a) 。
假设 b 是 a 的副本，并在末尾附加值 val。
题目数据保证 b 中的值互不相同。
返回 Construct(b)。
示例 1： 
输入：root = [4,1,3,null,null,2], val = 5
输出：[5,4,null,1,3,null,null,2]
解释：a = [1,4,2,3], b = [1,4,2,3,5]
示例 2： 
输入：root = [5,2,4,null,1], val = 3
输出：[5,2,4,null,1,null,3]
解释：a = [2,1,5,4], b = [2,1,5,4,3]
示例 3： 
输入：root = [5,2,3,null,1], val = 4
输出：[5,2,4,null,1,3]
解释：a = [2,1,5,3], b = [2,1,5,3,4]
提示：
-
树中节点数目在范围 内 -
-
树中的所有值 互不相同 -
模拟
题意不是很好理解，先稍微解释一下吧。
大概意思是最大树 root 是根据特定的规则构造出来的，即给定的 root 其实对应一个具体的 nums，题目要求是将 val 追加到 nums 的尾部，然后再对得到的 nums 运用相同规则的构造，返回重新构造的最大树头结点。
根据构造规则，若有下标
，则
必然在
水平线的左边，而 val 又是追加在原有 nums 的结尾。因此其最终位置分如下两种情况：
-
val为新nums中的最大值，同时val又是追加在原有nums的结尾，此时将原有的root挂在val对应节点的左子树即可，新树的根节点为val对应节点； -
否则，我们只需要不断在 root的右子树中找目标位置（反证法可以知，val必不可能出现在任一非右位置，否则可推断出在val右边仍有元素，这与val位于nums的结尾位置冲突）。假设目标位置的父节点为prev，目标位置的原节点为cur，根据构造规则可知prev.right = node且node.left = cur，新树的根节点不变。
Java 代码：
class Solution {
public TreeNode insertIntoMaxTree(TreeNode root, int val) {
TreeNode node = new TreeNode(val);
TreeNode prev = null, cur = root;
while (cur != null && cur.val > val) {
prev = cur; cur = cur.right;
}
if (prev == null) {
node.left = cur;
return node;
} else {
prev.right = node;
node.left = cur;
return root;
}
}
}
C++ 代码：
class Solution {
public:
TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
TreeNode* node = new TreeNode(val);
TreeNode* prev = nullptr;
TreeNode* cur = root;
while (cur != nullptr && cur->val > val) {
prev = cur; cur = cur->right;
}
if (prev == nullptr) {
node->left = cur;
return node;
} else {
prev->right = node;
node->left = cur;
return root;
}
}
};
Python 代码：
class Solution:
def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
node = TreeNode(val)
prev, cur = None, root
while cur is not None and cur.val > val:
prev = cur
cur = cur.right
if prev is None:
node.left = cur
return node
else:
prev.right = node
node.left = cur
return root
Typescript 代码：
function insertIntoMaxTree(root: TreeNode | null, val: number): TreeNode | null {
const node = new TreeNode(val)
let prev = null, cur = root
while (cur != null && cur.val > val) {
prev = cur; cur = cur.right
}
if (prev == null) {
node.left = root
return node
} else {
prev.right = node
node.left = cur
return root
}
};
-
时间复杂度： -
空间复杂度：
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
