Meta VO 面试真题解析：Binary Tree Boundary Traversal（树边界遍历）

Assume we have a Node class with:

• int val
• Node right
• Node left

Input: binary tree of ints (you’ll be given root node)

Return the boundary traversal of the binary tree.

Example:

Input:
      6
     / \
    3   4
   /   / \
  5   1   0
   \       /
    2     8
   / \
  9   7

Output:
[5, 9, 3, 2, 6, 1, 7, 4, 8, 0]

这题要求返回二叉树的边界遍历结果，也就是按“左边界（不含叶子）→ 所有叶子节点 → 右边界（不含叶子，逆序）”的顺序收集节点值，同时要避免重复加入叶子节点和根节点。常见做法是分别遍历左边界、叶子和右边界，整体复杂度为 O(n)，适合用 DFS 或递归配合少量辅助逻辑完成。