测试没测出来的 bug，为啥让开发背锅啊？？？

昨天晚上十一点多，在公司楼下吹风，手机电量只剩7%，小李给我发消息说：“哥，那个…二叉树前序遍历我老写错，面试要凉。”我当时脑子一紧，想了半秒：前序不就是“根—左—右”嘛。就是这个顺序，别想花里胡哨的。好，先说到这，回屋我把思路捋一下，顺便把Java代码扔给你们，别再被卡住了。

你们知道吧，树这种结构，人眼看是纵向的，但代码里其实就是节点连指针。前序遍历就是每到一个节点，先处理自己，再去左，再去右。像打卡一样：到此一游，左边看看，右边瞄瞄。空节点就别纠结，直接返回。复杂度…嗯，时间O(n)，每个节点看一次；空间看你用啥办法，递归是O(h)，h是树高，最坏退化链就是O(n)。这是基本盘。

说实话，面试官问基础，递归先写，快准稳。注意两点：判空别忘了；结果用一个list装着，别在方法里到处new。

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) { val = v; }
}

publicclass PreorderDemo {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        dfs(root, ans);
        return ans;
    }

    private void dfs(TreeNode node, List<Integer> ans) {
        if (node == null) return;
        ans.add(node.val);        // 根
        dfs(node.left, ans);      // 左
        dfs(node.right, ans);     // 右
    }
}

有人问我那个…尾递归能不能优化？Java编译器没给你自动优化的保证，别赌。栈太深会StackOverflow，所以面试官顺嘴一问“非递归呢”，你就要切换思路。

迭代其实就是你手动拿个栈模拟系统调用栈。顺序很讲究：因为栈后进先出，你得先压右，再压左，这样弹出来就是“根—左—右”。我刚才…咳，差点写反了。

public List<Integer> preorderTraversalIter(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) return ans;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode cur = stack.pop();
        ans.add(cur.val);                 // 先处理根
        if (cur.right != null) stack.push(cur.right); // 先右
        if (cur.left != null)  stack.push(cur.left);  // 后左
    }
    return ans;
}

这个版本好处是可控，不怕递归栈爆。但面试官可能追问边界：空树行不行？只有右子树行不行？都行，上面代码都兜住了。还有人把add写在压栈后面，那就不是前序了，别把自己绕晕。

就是那个…测试的时候，随手构一棵不平衡的树，左链或右链，看看空间和顺序。还有一个骚一点的写法叫Morris前序，空间O(1)，用线索二叉树把右指针临时改来改去，面试别主动秀，问到了再说，因为实现细节容易打错，临时指针恢复要小心。不想折腾就别上，稳一点。

另外，别在遍历里顺手System.out.println当答案交，真实业务里你要的是结果集合，不是打印。还有还有，List预分配容量没必要，树多大你也不知道，对吧。