华为各级OD薪资曝光。。

华为 OD 薪资

之前写过几篇华为 OD 的算法题，后来有不少同学问起，华为 OD 薪资到底怎么样。

华为 OD 的薪资待遇，网上信息不多，只找到一篇相对靠谱的爆料：

上述是月 base 的爆料，然后通常 OD 是 15-16 薪。

至于和正式员工的差别，以 14 级为例，正式员工基本在 20k 以上，而 OD 只有 13k-17k，但周末加班则是和正式员工一样，都是双倍。

网上信息很多，大多数都没有准确信息来源。之前有个说法十分流行，说华为 OD 曾在工作群中被骂道「你是外包不是正式员工，不要偷吃公司零食，注意素质」。

但根据目前掌握的信息来说，华为 OD 也是能享受常规待遇：

但股票分红这一块，华为 OD 自然是没有的。

...

回归主线。

来一道和「华为 OD」相关的面试原题。

题目描述

平台：LeetCode

题号：538

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左右子树也必须是二叉搜索树。

示例 1： alt

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]

输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：

输入：root = [0,null,1]

输出：[1,null,1]

提示：

树中的节点数在范围内。
树中的所有值均不重复。

中序遍历

利用 「BST 的中序遍历是有序」 的特性，我们可以通过两次遍历 BST 来求解问题。

首先，通过一次遍历，计算出整棵树的节点总和 tot，然后在中序遍历过程中，不断对 tot 进行更新，将其作为当前未遍历到的节点的总和，用于给当前节点赋值。

假设当前遍历到的节点为 x（起始节点值为 t），那么将节点更新为当前节点 tot 后，更新 tot = tot - t。

这是常规的中序遍历做法，更进一步，如果将其中序遍历的顺序进行翻转（从「左中右」调整为「右中左」），则可实现一次遍历。

Java 代码：

class Solution {
    int tot = 0;
    public TreeNode convertBST(TreeNode root) {
        dfs(root);
        return root;
    }
    void dfs(TreeNode root) {
        if (root == null) return ;
        dfs(root.right);
        tot += root.val;
        root.val = tot;
        dfs(root.left);
    }
}

C++ 代码：

class Solution {
public:
    int tot = 0;
    TreeNode* convertBST(TreeNode* root) {
        dfs(root);
        return root;
    }
    void dfs(TreeNode* root) {
        if (root == nullptr) return;
        dfs(root->right);
        tot += root->val;
        root->val = tot;
        dfs(root->left);
    }
};

Python 代码：

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        tot = 0
        def dfs(root):
            nonlocal tot
            if not root: return
            dfs(root.right)
            tot += root.val
            root.val = tot
            dfs(root.left)
        dfs(root)
        return root

TypeScript 代码：

function convertBST(root: TreeNode | null): TreeNode | null {
    let tot = 0;
    const dfs = function(root: TreeNode | null): void {
        if (!root) return ;
        dfs(root.right);
        tot += root.val;
        root.val = tot;
        dfs(root.left);
    }
    dfs(root);
    return root;
};