题目重点：Phone Coding 题目说 LC 545 的变体并限定 full/complete/balanced tree；本文先按标准逆时针边界训练，拆左边界、叶子和反向右边界。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版输出逆时针边界：根、左边界非叶、从左到右所有叶、右边界非叶逆序；每节点只出现一次。
- 节点有唯一整数 value 便于测试；真实题可能允许重复值，算法应按节点身份而非值去重。
- 题目称 full/complete/balanced，但没有定义这些词组合是否等同完美二叉树；代码支持任意二叉树，因此涵盖该特例，不能宣称其特殊条件被完整还原。
解题路线
- 空树返回空；单节点树只输出一次。一般情形先记录根。
- 从 root.left 往下，优先走 left，否则走 right；只把非叶加入左边界，以免叶子后续重复。
- 对整棵树做左先的 DFS，仅收叶子，得到从左至右顺序；示例用显式栈，压右再压左。
- 从 root.right 往下优先走 right，否则走 left，收非叶到临时数组，最后逆序接到结果。
- 对 full/complete/balanced 特例也保持一般算法，讨论其高度 O(log N) 但全部叶子仍需 O(N) 时间；10,000 组随机树与独立递归路径+叶子参考对照。
手动走一遍
根 1，左子树 2→(4,5)，右子树 3→(6,7)。根=[1]，左边界非叶=[2]，叶子=[4,5,6,7]，右边界逆序=[3]，输出 [1,2,4,5,6,7,3]；不要把 4 和 7 再算进边界。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Boundary of a binary tree, counterclockwise, without duplicate leaves."""
from dataclasses import dataclass
@dataclass
class Node:
value: int
left: "Node | None" = None
right: "Node | None" = None
def boundary(root: Node | None) -> list[int]:
if root is None:
return []
result = [root.value]
if root.left is None and root.right is None:
return result
node = root.left
while node is not None:
if node.left is not None or node.right is not None:
result.append(node.value)
node = node.left if node.left is not None else node.right
stack = [root]
while stack:
node = stack.pop()
if node.left is None and node.right is None and node is not root:
result.append(node.value)
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 node.left is not None or node.right is not None:
right.append(node.value)
node = node.right if node.right is not None else node.left
result.extend(reversed(right))
return result
复杂度
每节点至多在叶子遍历被访问一次，边界路径再访问 O(h) 个节点，总 O(N) 时间；显式 DFS 栈在最坏斜树为 O(h)，右边界缓冲 O(h)，输出 O(B)，其中 B 为边界节点数。若确为完整平衡树，h=O(log N)。
易错点与追问
容易失分的边界
- 根是叶子时收根又收叶，重复输出。
- 左/右边界把叶节点加入，再由叶子遍历重复加入。
- 右边界没有逆序，输出变成自顶向下而非逆时针。
- 用 value 去重，合法重复值会被误删。
- 把 full、complete、balanced 三词未经确认就硬判成同一树形。
继续深挖
- 如果输出顺时针边界，三段顺序和走法如何变？
- 若树节点有 parent 指针，能否 O(1) 额外空间遍历？代价是什么？
- 如果原题只要求所有叶节点的和，是否还需边界路径？
- full、complete、perfect 分别有什么定义，哪些能从题面推出？
