Meta 二叉树侧视图：左右边界与逆序变体

题意与假设

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

• 普通二叉树，左/右侧视图都是每一层一个可见节点，按根到叶输出；若要求底到顶最后reverse对应结果。
• 侧视图不是二叉树boundary：boundary还包含所有叶及外侧路径，不能混同。未描述的其它199变体保留待核。

解题路线

1. BFS一层固定width，每层按left再right入队，处理第0个记leftView、第width−1个记rightView。
2. 左右视图共享一次遍历；节点值重复仍每层保留一个，不能set去重。
3. DFS也可首次到达depth记结果，左优先得左视图、右优先得右视图；更省宽度空间但深树栈更深。

手动走一遍

根1、左2、右3，左2的右孩子4、右3无孩子：左视图[1,2,4]，右视图[1,3,4]。同一节点4可以同时在两侧，不代表需要在一个合并结果中重复列。

Python 参考实现

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

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

from collections import deque


def side_views(root):
    """Return left/right view TOP to bottom. Reverse either explicitly if requested."""
    if root is None:return [],[]
    queue=deque([root]);left=[];right=[]
    while queue:
        width=len(queue)
        for i in range(width):
            node=queue.popleft()
            if i==0:left.append(node.val)
            if i==width-1:right.append(node.val)
            if node.left is not None:queue.append(node.left)
            if node.right is not None:queue.append(node.right)
    return left,right

复杂度

BFS O(n)时间/O(maxWidth)队列，结果O(h)；DFS O(n)/O(h)调用栈。

易错点与追问

容易失分的边界

• 只沿root.right向下会漏掉右子为空而左子更深的可见节点。
• 逆序只改变输出顺序，不改变每层选最左/最右的判断。

继续深挖

• 若返回左右交替的层展示，应另定输出是两个数组还是每层pair，避免混合成zigzag遍历。
• 若每节点有N个有序孩子，BFS每层首尾逻辑仍可用。