Solve Bracket Matching and Tree Width

Solve both coding problems below. ## Problem 1: Validate Balanced Brackets Given a string `s` containing only the characters `(`, `)`, `{`, `}`, `[` and `]`, determine whether the brackets are valid. A string is valid if: 1. Every opening bracket is closed by the same type of bracket. 2. Opening brackets are closed in the correct order. 3. Every closing bracket has a corresponding previous opening bracket. Return `true` if the string is valid; otherwise return `false`. ### Examples ```text Input: s = "()[]{}" Output: true ``` ```text Input: s = "([)]" Output: false ``` ```text Input: s = "{[]}" Output: true ``` ### Constraints - `0 <= s.length <= 100000` - `s` contains only bracket characters. --- ## Problem 2: Compute the Maximum Level Span in a Binary Tree You are given the root of a binary tree. For each depth level, imagine the tree is placed into a full binary tree layout where the root has position index `0`, a node at index `i` has left child index `2 * i` and right child index `2 * i + 1`. The span of a level is: ```text rightmost_position_index - leftmost_position_index + 1 ``` This span includes the gaps between existing nodes. Return the maximum span among all levels. ### Example ```text Input tree: 1 / \ 3 2 / \ 5 9 Position indexes by level: Level 0: 1 at index 0, span = 1 Level 1: 3 at index 0, 2 at index 1, span = 2 Level 2: 5 at index 0, 9 at index 3, span = 4 Output: 4 ``` ### Constraints - The number of nodes is between `0` and `100000`. - Node values are irrelevant. - Your solution should run in `O(n)` time, where `n` is the number of nodes. - Be careful to avoid integer overflow when assigning position indexes.