外包年薪 30万，体制内年薪10万，选哪个比较好?

刚看到个贴子，说程序员一个是外包年薪30万，一个是体制内年薪10万，到底选哪个。

网友说得挺实在：“你穷就选工资高的，家里有点资产就选体制内。”

我觉得这话虽然糙，但挺有道理。外包的钱多，可是项目紧、加班多，像在坐过山车；体制内稳定，但节奏慢、涨薪慢，就像坐公交，稳是稳，跑不快。关键看你想要啥。要积累、要翻身，先去外包拼几年；要安稳、要生活，体制内更适合。

人生不同阶段有不同选择，只要清楚自己要什么，不眼红别人，就不算选错路。【备注:文末可领最新资料】

昨晚十一点多在公司楼下吹风，手机一震，小李问我：东哥，那个“把二叉搜索树改成累加树”的题到底咋写啊？我一愣，这题不难，但老有人卡在细节上。就用最顺嘴的说法跟你唠一下，别紧张，思路很朴素。

你手里是一棵二叉搜索树（BST），右边都比根大、左边都比根小，对吧。现在要改造成“累加树”：每个节点的值换成“原树里所有 ≥ 它 的节点值之和”。比如你站在 7 这个点，新的 7 就等于 {7、8、9…右边那些} 的总和。就这一个规则。

反中序一路加

因为 BST 右侧更大，那就从右往左遍历：右→根→左。路上扛着一个“滚动和”sum，见一个点就把它原值加进 sum，然后把节点值改成 sum。这样保证你更新当前点时，右边的大哥们都已经算完并堆到 sum 里了。就是这么直给。

classSolution{
// 也有人写成 long，数据大就换 long
privateint acc = 0;

public TreeNode convertBST(TreeNode root){
// 反中序遍历：右 -> 根 -> 左
        dfs(root);
return root;
    }

privatevoiddfs(TreeNode node){
if (node == null) return;
        dfs(node.right);
        acc += node.val;     // 累加右边和自己
        node.val = acc;      // 把新值写回去
        dfs(node.left);
    }
}

// 常见的节点结构
classTreeNode{
int val;
    TreeNode left, right;
    TreeNode(int v){ this.val = v; }
}

来个迭代版

递归怕栈深度？用栈模拟也行，仍旧右→根→左：

classSolutionIter{
public TreeNode convertBST(TreeNode root){
int acc = 0;
        java.util.Deque<TreeNode> stack = new java.util.ArrayDeque<>();
        TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) { // 一路向右
                stack.push(cur);
                cur = cur.right;
            }
            cur = stack.pop();
            acc += cur.val;
            cur.val = acc;
            cur = cur.left; // 再转向左
        }
return root;
    }
}

几个小坑

1）溢出：节点值范围大就把 int acc 换成 long，必要时节点值也用 long。 2）原地修改：题目默认你能改原树，别另外抄一棵，省空间。 3）空树：别忘了 null 直接回 null，测例会这么整你一次。 4）复杂度：两种写法都是 O(n)；递归空间最坏 O(h)，迭代也是 O(h)，h 是树高。

行了，核心就这些。右边先走，边走边加，回头把值写回去，像数钱一样。等会我去泡个茶，你要是想看 Morris 不开栈那版，也能给你整，不过一般面试不强求。