卧槽，这就是上海的工资水平吗？

有个大厂员工在那儿感叹，上海现在这工资水平也太离谱了吧，平均月薪都干到3万了。

有人直接破防：合着我在上海呼吸这么多年，平均值是一点没把我当人算啊。

这玩意儿最扎心的地方就在这儿。你看“平均3万”四个字，挺光鲜，像大家都混得不错。结果一落到自己工资条上，瞬间清醒。房租扣一截，通勤耗一截，吃饭社交再来一刀，月底一看余额，沉默了。

可问题是，天花板高不代表人人都站在梯子上。很多人只是站在楼下仰头看，脖子都酸了。

所以看到平均月薪3万，我第一反应不是嫉妒，是想问一句：这平均值到底是谁在疯狂输出啊。

二叉树的边界，这题看着像遍历，真写起来很容易多加一个节点。

最常见的翻车现场就是：根节点加了一次，叶子节点又加了一次；右边界正着加，结果顺序反了；左边界一路找 left，遇到空了不知道该不该转 right。

我一般不把它当成一个 DFS 模板题看，而是拆成三段现场处理：

根节点先放进去。

左边界从 root.left 开始走，只收非叶子节点。

叶子节点单独 DFS，从左到右收。

右边界从 root.right 开始走，也只收非叶子节点，但最后要倒着放回结果里。

边界的顺序是逆时针的：

root -> 左边界 -> 所有叶子 -> 右边界反向

这里最烦的是“叶子节点重复”。比如左边界最后一个节点本身就是叶子，如果左边界收了它，后面叶子 DFS 又会收一次。所以边界遍历里我直接把叶子排除掉，叶子统一交给 DFS。

代码可以这样写：

import java.util.*;

classSolution{
public List<Integer> boundaryOfBinaryTree(TreeNode root){
        List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
        }

        ans.add(root.val);

        collectLeft(root.left, ans);

if (!isLeaf(root)) {
            collectLeaves(root, ans);
        }

        List<Integer> right = new ArrayList<>();
        collectRight(root.right, right);
for (int i = right.size() - 1; i >= 0; i--) {
            ans.add(right.get(i));
        }

return ans;
    }

privatevoidcollectLeft(TreeNode node, List<Integer> ans){
while (node != null) {
if (!isLeaf(node)) {
                ans.add(node.val);
            }

if (node.left != null) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
    }

privatevoidcollectRight(TreeNode node, List<Integer> right){
while (node != null) {
if (!isLeaf(node)) {
                right.add(node.val);
            }

if (node.right != null) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
    }

privatevoidcollectLeaves(TreeNode node, List<Integer> ans){
if (node == null) {
return;
        }

if (isLeaf(node)) {
            ans.add(node.val);
return;
        }

        collectLeaves(node.left, ans);
        collectLeaves(node.right, ans);
    }

privatebooleanisLeaf(TreeNode node){
return node != null && node.left == null && node.right == null;
    }
}

这个写法不花哨，但边界很清楚。

左边界有个细节：不是只走 left。比如这棵树：

    1
   /
  2
   \
    3

节点 3 其实也在左边界上，因为 2 没有 left，只能往 right 贴着外侧走。右边界同理，优先走 right，right 没有再走 left。

再看一个容易误判的情况：

    1
   / \
  2   3

结果应该是：

[1, 2, 3]

不是 [1, 2, 2, 3, 3]。所以我才会把左边界、右边界里的叶子过滤掉，叶子只在 collectLeaves 里统一收。

这题时间复杂度就是 O(n)，每个节点最多被扫到常数次。空间复杂度主要看递归栈，最坏退化成链表是 O(n)。

真正写的时候别急着一把 DFS 搞完。边界题最怕“逻辑看着统一”，最后在重复节点和顺序上补丁越打越多。拆成三段，反而不容易错。