Practice/Amazon/Leetcode 545. Boundary of Binary Tree

Leetcode 545. Boundary of Binary Tree

CodingMust

Problem

Given the root of a binary tree, return an array representing the perimeter of the tree viewed in a counter-clockwise direction starting from the root.

The perimeter consists of three parts in order:

1. Left boundary: All nodes on the path from the root to the leftmost node (excluding leaf nodes), traversed top-down
2. Leaf nodes: All leaf nodes from left to right
3. Right boundary: All nodes on the path from the root to the rightmost node (excluding leaf nodes), traversed bottom-up

Important: The root should only appear once, and no node should be duplicated in the result.

Requirements

1. Return nodes in the exact order: left boundary (top-down), then leaves (left-to-right), then right boundary (bottom-up)
2. Exclude leaf nodes from the left and right boundaries (they're added separately in the leaves section)
3. Handle edge cases where the tree is single-node, left-skewed, or right-skewed
4. The root node should appear exactly once, even if it's also a leaf

Constraints

• The number of nodes in the tree is in the range [1, 10000]
• -1000 <= Node.val <= 1000
• Time complexity should be O(n) where n is the number of nodes
• Space complexity should be O(h) where h is the height of the tree (excluding output array)

Examples

Example 1:

` Input: root = [1,2,3,4,5,6,7,8,9,10] 1 /
2 3 / \ /
4 5 6 7 /
8 9 10

Output: [1,2,4,8,9,10,6,7,3] Explanation:

• Left boundary (excluding leaves): [1,2,4]
• Leaves (left to right): [8,9,10,6,7]
• Right boundary (excluding leaves, bottom-up): [3] `

Example 2:

Input: root = [1] Output: [1] Explanation: A single node is both root and leaf, so it appears once.

Example 3:

` Input: root = [1,2,3,4,null,null,5] 1 /
2 3 /
4 5

Output: [1,2,4,5,3] Explanation:

• Left boundary (excluding leaves): [1,2]
• Leaves: [4,5]
• Right boundary (excluding leaves, bottom-up): [3] `