Meta 树的边界：左边、叶子与右边逆序去重

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练root→非叶左边界→所有叶左到右→非叶右边界逆序；值可重复但节点身份不同，空[]、单节点仅一次root。
• 题目标签未披露具体边界变体，本文使用此明确标准训练合同，不把side view当boundary。

解题路线

1. root单独写一次；从root.left走优先left否则right，非叶加入左边界；从root.right优先right否则left，非叶收集后reverse。
2. 独立DFS所有叶子按left-first输出，左右boundary跳过leaf避免两端叶重复。root为leaf单独返回，否则不会在叶步骤重复root。
3. 缺左child不从root.right补左边界，右侧仍按右边界逆序，否则单右链节点会重复/顺序错误。boundary与每层侧视图不同，不取所有每层最左节点。
4. 值相同不能set去重，否则不同边界节点被丢掉；结构去重来自分段规则而不是数值集合。

手动走一遍

单右链1→2→3边界为1,3,2：root、leaf、右边界逆序。单节点1仅[1]。一般两侧有共同leaf段时左/右收集都跳叶，叶DFS只输出一次。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def boundary(root):
    """Counterclockwise: root, nonleaf left edge, all leaves, reversed right edge."""
    if root is None:return []
    leaf=lambda node:node.left is None and node.right is None
    if leaf(root):return [root.value]
    result=[root.value];node=root.left
    while node is not None:
        if not leaf(node):result.append(node.value)
        node=node.left if node.left is not None else node.right
    stack=[root]
    while stack:
        node=stack.pop()
        if leaf(node):result.append(node.value)
        else:
            if node.right is not None:stack.append(node.right)
            if node.left is not None:stack.append(node.left)
    right=[];node=root.right
    while node is not None:
        if not leaf(node):right.append(node.value)
        node=node.right if node.right is not None else node.left
    result.extend(reversed(right));return result

复杂度

O(N)叶遍历加O(h)两侧边界，辅助O(h)DFS/right收集，输出O(边界节点数)。最坏全树都边界，输出O(N)，不能因不是所有节点都输出就说次线性遍历。

易错点与追问

容易失分的边界

• 左/右都收叶再DFS，端点重复。
• 用value set去重破坏同值节点。
• boundary等同left/right view会取错误中间节点。

继续深挖

• 要求顺时针时分段顺序和每段方向怎样改？
• 仅返回轮廓而不含内部叶的变体，为什么需先给定义？