某程序员自爆:两个工作机会，一个是大厂自研月薪21K，一个是外包27K，外包工作更舒服，该怎么选?

那个树…二叉树…同事小李问我：字符串能不能直接还原成树？我嘴一瓢：“能啊，用括号那种——就像 1(2(4)(#))(3(#)(5))，#表示空，挺顺手的。”说着手就痒了，回工位糊了段 Java，顺便把坑也补上。

别纠结花里胡哨，咱就一种简单规约：val(left)(right)，左右子树都用一对小括号包起来；空节点就是 #；支持负数，比如 -12(#)(7)。这样好处是…嗯…递归一层对应一对括号，肉眼也能跟。

就是“指针”往前扫：先读一个整数当根；

• 接着如果看到 ( 就进去递归，出来时得对上 )；
• 连续两次就是左、右；
• 碰到 # 就是空，记得把括号吃掉。 为了不把索引传来传去，我用一个可变下标对象，走到哪记到哪。

import java.util.*;

classTreeNode{
int val;
    TreeNode left, right;
    TreeNode(int v) { this.val = v; }
}

publicclassBuildTreeFromString{
// 可变索引，模拟“指针”
staticclassIdx{ int i = 0; }

publicstatic TreeNode build(String s){
if (s == null || s.isEmpty()) returnnull;
        Idx idx = new Idx();
return parse(s, idx);
    }

privatestatic TreeNode parse(String s, Idx idx){
        skipSpace(s, idx);
if (idx.i >= s.length()) returnnull;

// 空节点： #(…) 或 单独 #
if (s.charAt(idx.i) == '#') { idx.i++; returnnull; }

// 读整数（含负号）
int sign = 1;
if (s.charAt(idx.i) == '-') { sign = -1; idx.i++; }
int num = 0; boolean hasDigit = false;
while (idx.i < s.length() && Character.isDigit(s.charAt(idx.i))) {
            num = num * 10 + (s.charAt(idx.i) - '0');
            idx.i++; hasDigit = true;
        }
if (!hasDigit) thrownew IllegalArgumentException("缺少节点值，位置：" + idx.i);
        TreeNode root = new TreeNode(sign * num);

// 解析左子树：期望 '(' left ')'
        skipSpace(s, idx);
if (idx.i < s.length() && s.charAt(idx.i) == '(') {
            idx.i++; // 吃 '('
            root.left = parse(s, idx);
            expectRightParen(s, idx);
        }

// 解析右子树：期望 '(' right ')'
        skipSpace(s, idx);
if (idx.i < s.length() && s.charAt(idx.i) == '(') {
            idx.i++; // 吃 '('
            root.right = parse(s, idx);
            expectRightParen(s, idx);
        }
return root;
    }

privatestaticvoidexpectRightParen(String s, Idx idx){
        skipSpace(s, idx);
if (idx.i >= s.length() || s.charAt(idx.i) != ')')
thrownew IllegalArgumentException("少了一个右括号 )，位置：" + idx.i);
        idx.i++; // 吃 ')'
    }

privatestaticvoidskipSpace(String s, Idx idx){
while (idx.i < s.length() && Character.isWhitespace(s.charAt(idx.i))) idx.i++;
    }

// 小工具：层序输出，方便瞄一眼结果
publicstatic String levelOrder(TreeNode root){
if (root == null) return"[]";
        List<String> out = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
while (!q.isEmpty()) {
            TreeNode n = q.poll();
if (n == null) { out.add("null"); continue; }
            out.add(String.valueOf(n.val));
            q.add(n.left);
            q.add(n.right);
        }
int k = out.size() - 1;
while (k >= 0 && "null".equals(out.get(k))) k--;
return"[" + String.join(",", out.subList(0, k + 1)) + "]";
    }

// 随手测一下
publicstaticvoidmain(String[] args){
        String s = "1(2(4)(#))(3(#)(5))";
        TreeNode root = build(s);
        System.out.println(levelOrder(root)); // [1,2,3,4,null,null,5]
    }
}

昨晚困得眼冒金星…还是把这仨坑填了： 1）负数别漏了 -；2）空节点用 # 时，括号也要匹配，比如 ( # ) 可以写成 (#)；3）括号校验出错别悄悄吞，直接抛异常，省得半夜追日志。

嗯…那就是 level-order 格式（[1,2,3,null,4]）+ 队列重建，思路不冲突，只是入口不一样。上面这个括号法更贴近递归结构，看起来清爽。好了不啰嗦，我去泡杯茶，等会儿再改个 Bug…

-END-

我为大家打造了一份RPA教程，完全免费：songshuhezi.com/rpa.html