bowang0911/leetcode huggingface dataset:
Remove Duplicates from Sorted Array II

Given an integer array `nums` sorted in **non-decreasing order**, remove some duplicates [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm) such that each unique element appears **at most twice**. The **relative order** of the elements should be kept the **same**.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the **first part** of the array `nums`. More formally, if there are `k` elements after removing the duplicates, then the first `k` elements of `nums` should hold the final result. It does not matter what you leave beyond the first `k` elements.

Return `k` _after placing the final result in the first_ `k` _slots of_ `nums`.

Do **not** allocate extra space for another array. You must do this by **modifying the input array [in-place](https://en.wikipedia.org/wiki/In-place_algorithm)** with O(1) extra memory.

**Custom Judge:**

The judge will test your solution with the following code:

int\[\] nums = \[...\]; // Input array
int\[\] expectedNums = \[...\]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums\[i\] == expectedNums\[i\];
}

If all assertions pass, then your solution will be **accepted**.

**Example 1:**

**Input:** nums = \[1,1,1,2,2,3\]
**Output:** 5, nums = \[1,1,2,2,3,\_\]
**Explanation:** Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

**Example 2:**

**Input:** nums = \[0,0,1,1,1,1,2,3,3\]
**Output:** 7, nums = \[0,0,1,1,2,3,3,\_,\_\]
**Explanation:** Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

**Constraints:**

*   `1 <= nums.length <= 3 * 104`
*   `-104 <= nums[i] <= 104`
*   `nums` is sorted in **non-decreasing** order.
Search in Rotated Sorted Array II

There is an integer array `nums` sorted in non-decreasing order (not necessarily with **distinct** values).

Before being passed to your function, `nums` is **rotated** at an unknown pivot index `k` (`0 <= k < nums.length`) such that the resulting array is `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]` (**0-indexed**). For example, `[0,1,2,4,4,4,5,6,6,7]` might be rotated at pivot index `5` and become `[4,5,6,6,7,0,1,2,4,4]`.

Given the array `nums` **after** the rotation and an integer `target`, return `true` _if_ `target` _is in_ `nums`_, or_ `false` _if it is not in_ `nums`_._

You must decrease the overall operation steps as much as possible.

**Example 1:**

**Input:** nums = \[2,5,6,0,0,1,2\], target = 0
**Output:** true

**Example 2:**

**Input:** nums = \[2,5,6,0,0,1,2\], target = 3
**Output:** false

**Constraints:**

*   `1 <= nums.length <= 5000`
*   `-104 <= nums[i] <= 104`
*   `nums` is guaranteed to be rotated at some pivot.
*   `-104 <= target <= 104`

**Follow up:** This problem is similar to Search in Rotated Sorted Array, but `nums` may contain **duplicates**. Would this affect the runtime complexity? How and why?
Remove Duplicates from Sorted List II

Given the `head` of a sorted linked list, _delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list_. Return _the linked list **sorted** as well_.

**Example 1:**

**Input:** head = \[1,2,3,3,4,4,5\]
**Output:** \[1,2,5\]

**Example 2:**

**Input:** head = \[1,1,1,2,3\]
**Output:** \[2,3\]

**Constraints:**

*   The number of nodes in the list is in the range `[0, 300]`.
*   `-100 <= Node.val <= 100`
*   The list is guaranteed to be **sorted** in ascending order.
Remove Duplicates from Sorted List

Given the `head` of a sorted linked list, _delete all duplicates such that each element appears only once_. Return _the linked list **sorted** as well_.

**Example 1:**

**Input:** head = \[1,1,2\]
**Output:** \[1,2\]

**Example 2:**

**Input:** head = \[1,1,2,3,3\]
**Output:** \[1,2,3\]

**Constraints:**

*   The number of nodes in the list is in the range `[0, 300]`.
*   `-100 <= Node.val <= 100`
*   The list is guaranteed to be **sorted** in ascending order.
Largest Rectangle in Histogram

Given an array of integers `heights` representing the histogram's bar height where the width of each bar is `1`, return _the area of the largest rectangle in the histogram_.

**Example 1:**

**Input:** heights = \[2,1,5,6,2,3\]
**Output:** 10
**Explanation:** The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

**Example 2:**

**Input:** heights = \[2,4\]
**Output:** 4

**Constraints:**

*   `1 <= heights.length <= 105`
*   `0 <= heights[i] <= 104`
Maximal Rectangle

Given a `rows x cols` binary `matrix` filled with `0`'s and `1`'s, find the largest rectangle containing only `1`'s and return _its area_.

**Example 1:**

**Input:** matrix = \[\[ "1 ", "0 ", "1 ", "0 ", "0 "\],\[ "1 ", "0 ", "1 ", "1 ", "1 "\],\[ "1 ", "1 ", "1 ", "1 ", "1 "\],\[ "1 ", "0 ", "0 ", "1 ", "0 "\]\]
**Output:** 6
**Explanation:** The maximal rectangle is shown in the above picture.

**Example 2:**

**Input:** matrix = \[\[ "0 "\]\]
**Output:** 0

**Example 3:**

**Input:** matrix = \[\[ "1 "\]\]
**Output:** 1

**Constraints:**

*   `rows == matrix.length`
*   `cols == matrix[i].length`
*   `1 <= row, cols <= 200`
*   `matrix[i][j]` is `'0'` or `'1'`.
Partition List

Given the `head` of a linked list and a value `x`, partition it such that all nodes **less than** `x` come before nodes **greater than or equal** to `x`.

You should **preserve** the original relative order of the nodes in each of the two partitions.

**Example 1:**

**Input:** head = \[1,4,3,2,5,2\], x = 3
**Output:** \[1,2,2,4,3,5\]

**Example 2:**

**Input:** head = \[2,1\], x = 2
**Output:** \[1,2\]

**Constraints:**

*   The number of nodes in the list is in the range `[0, 200]`.
*   `-100 <= Node.val <= 100`
*   `-200 <= x <= 200`
Scramble String

We can scramble a string s to get a string t using the following algorithm:

1.  If the length of the string is 1, stop.
2.  If the length of the string is > 1, do the following:
    *   Split the string into two non-empty substrings at a random index, i.e., if the string is `s`, divide it to `x` and `y` where `s = x + y`.
    *   **Randomly** decide to swap the two substrings or to keep them in the same order. i.e., after this step, `s` may become `s = x + y` or `s = y + x`.
    *   Apply step 1 recursively on each of the two substrings `x` and `y`.

Given two strings `s1` and `s2` of **the same length**, return `true` if `s2` is a scrambled string of `s1`, otherwise, return `false`.

**Example 1:**

**Input:** s1 =  "great ", s2 =  "rgeat "
**Output:** true
**Explanation:** One possible scenario applied on s1 is:
 "great " -->  "gr/eat " // divide at random index.
 "gr/eat " -->  "gr/eat " // random decision is not to swap the two substrings and keep them in order.
 "gr/eat " -->  "g/r / e/at " // apply the same algorithm recursively on both substrings. divide at random index each of them.
 "g/r / e/at " -->  "r/g / e/at " // random decision was to swap the first substring and to keep the second substring in the same order.
 "r/g / e/at " -->  "r/g / e/ a/t " // again apply the algorithm recursively, divide  "at " to  "a/t ".
 "r/g / e/ a/t " -->  "r/g / e/ a/t " // random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is  "rgeat " which is s2.
As one possible scenario led s1 to be scrambled to s2, we return true.

**Example 2:**

**Input:** s1 =  "abcde ", s2 =  "caebd "
**Output:** false

**Example 3:**

**Input:** s1 =  "a ", s2 =  "a "
**Output:** true

**Constraints:**

*   `s1.length == s2.length`
*   `1 <= s1.length <= 30`
*   `s1` and `s2` consist of lowercase English letters.
Merge Sorted Array

You are given two integer arrays `nums1` and `nums2`, sorted in **non-decreasing order**, and two integers `m` and `n`, representing the number of elements in `nums1` and `nums2` respectively.

**Merge** `nums1` and `nums2` into a single array sorted in **non-decreasing order**.

The final sorted array should not be returned by the function, but instead be _stored inside the array_ `nums1`. To accommodate this, `nums1` has a length of `m + n`, where the first `m` elements denote the elements that should be merged, and the last `n` elements are set to `0` and should be ignored. `nums2` has a length of `n`.

**Example 1:**

**Input:** nums1 = \[1,2,3,0,0,0\], m = 3, nums2 = \[2,5,6\], n = 3
**Output:** \[1,2,2,3,5,6\]
**Explanation:** The arrays we are merging are \[1,2,3\] and \[2,5,6\].
The result of the merge is \[1,2,2,3,5,6\] with the underlined elements coming from nums1.

**Example 2:**

**Input:** nums1 = \[1\], m = 1, nums2 = \[\], n = 0
**Output:** \[1\]
**Explanation:** The arrays we are merging are \[1\] and \[\].
The result of the merge is \[1\].

**Example 3:**

**Input:** nums1 = \[0\], m = 0, nums2 = \[1\], n = 1
**Output:** \[1\]
**Explanation:** The arrays we are merging are \[\] and \[1\].
The result of the merge is \[1\].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

**Constraints:**

*   `nums1.length == m + n`
*   `nums2.length == n`
*   `0 <= m, n <= 200`
*   `1 <= m + n <= 200`
*   `-109 <= nums1[i], nums2[j] <= 109`

**Follow up:** Can you come up with an algorithm that runs in `O(m + n)` time?
Gray Code

An **n-bit gray code sequence** is a sequence of `2n` integers where:

*   Every integer is in the **inclusive** range `[0, 2n - 1]`,
*   The first integer is `0`,
*   An integer appears **no more than once** in the sequence,
*   The binary representation of every pair of **adjacent** integers differs by **exactly one bit**, and
*   The binary representation of the **first** and **last** integers differs by **exactly one bit**.

Given an integer `n`, return _any valid **n-bit gray code sequence**_.

**Example 1:**

**Input:** n = 2
**Output:** \[0,1,3,2\]
**Explanation:**
The binary representation of \[0,1,3,2\] is \[00,01,11,10\].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit
\[0,2,3,1\] is also a valid gray code sequence, whose binary representation is \[00,10,11,01\].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit

**Example 2:**

**Input:** n = 1
**Output:** \[0,1\]

**Constraints:**

*   `1 <= n <= 16`
Subsets II

Given an integer array `nums` that may contain duplicates, return _all possible_ _subsets_ _(the power set)_.

The solution set **must not** contain duplicate subsets. Return the solution in **any order**.

**Example 1:**

**Input:** nums = \[1,2,2\]
**Output:** \[\[\],\[1\],\[1,2\],\[1,2,2\],\[2\],\[2,2\]\]

**Example 2:**

**Input:** nums = \[0\]
**Output:** \[\[\],\[0\]\]

**Constraints:**

*   `1 <= nums.length <= 10`
*   `-10 <= nums[i] <= 10`
Decode Ways

A message containing letters from `A-Z` can be **encoded** into numbers using the following mapping:

'A' ->  "1 "
'B' ->  "2 "
...
'Z' ->  "26 "

To **decode** an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, `"11106 "` can be mapped into:

*   `"AAJF "` with the grouping `(1 1 10 6)`
*   `"KJF "` with the grouping `(11 10 6)`

Note that the grouping `(1 11 06)` is invalid because `"06 "` cannot be mapped into `'F'` since `"6 "` is different from `"06 "`.

Given a string `s` containing only digits, return _the **number** of ways to **decode** it_.

The test cases are generated so that the answer fits in a **32-bit** integer.

**Example 1:**

**Input:** s =  "12 "
**Output:** 2
**Explanation:**  "12 " could be decoded as  "AB " (1 2) or  "L " (12).

**Example 2:**

**Input:** s =  "226 "
**Output:** 3
**Explanation:**  "226 " could be decoded as  "BZ " (2 26),  "VF " (22 6), or  "BBF " (2 2 6).

**Example 3:**

**Input:** s =  "06 "
**Output:** 0
**Explanation:**  "06 " cannot be mapped to  "F " because of the leading zero ( "6 " is different from  "06 ").

**Constraints:**

*   `1 <= s.length <= 100`
*   `s` contains only digits and may contain leading zero(s).
Reverse Linked List II

Given the `head` of a singly linked list and two integers `left` and `right` where `left <= right`, reverse the nodes of the list from position `left` to position `right`, and return _the reversed list_.

**Example 1:**

**Input:** head = \[1,2,3,4,5\], left = 2, right = 4
**Output:** \[1,4,3,2,5\]

**Example 2:**

**Input:** head = \[5\], left = 1, right = 1
**Output:** \[5\]

**Constraints:**

*   The number of nodes in the list is `n`.
*   `1 <= n <= 500`
*   `-500 <= Node.val <= 500`
*   `1 <= left <= right <= n`

**Follow up:** Could you do it in one pass?
Restore IP Addresses

A **valid IP address** consists of exactly four integers separated by single dots. Each integer is between `0` and `255` (**inclusive**) and cannot have leading zeros.

*   For example, `"0.1.2.201 "` and `"192.168.1.1 "` are **valid** IP addresses, but `"0.011.255.245 "`, `"192.168.1.312 "` and `"192.168@1.1 "` are **invalid** IP addresses.

Given a string `s` containing only digits, return _all possible valid IP addresses that can be formed by inserting dots into_ `s`. You are **not** allowed to reorder or remove any digits in `s`. You may return the valid IP addresses in **any** order.

**Example 1:**

**Input:** s =  "25525511135 "
**Output:** \[ "255.255.11.135 ", "255.255.111.35 "\]

**Example 2:**

**Input:** s =  "0000 "
**Output:** \[ "0.0.0.0 "\]

**Example 3:**

**Input:** s =  "101023 "
**Output:** \[ "1.0.10.23 ", "1.0.102.3 ", "10.1.0.23 ", "10.10.2.3 ", "101.0.2.3 "\]

**Constraints:**

*   `1 <= s.length <= 20`
*   `s` consists of digits only.
Binary Tree Inorder Traversal

Given the `root` of a binary tree, return _the inorder traversal of its nodes' values_.

**Example 1:**

**Input:** root = \[1,null,2,3\]
**Output:** \[1,3,2\]

**Example 2:**

**Input:** root = \[\]
**Output:** \[\]

**Example 3:**

**Input:** root = \[1\]
**Output:** \[1\]

**Constraints:**

*   The number of nodes in the tree is in the range `[0, 100]`.
*   `-100 <= Node.val <= 100`

**Follow up:** Recursive solution is trivial, could you do it iteratively?
Unique Binary Search Trees II

Given an integer `n`, return _all the structurally unique **BST'**s (binary search trees), which has exactly_ `n` _nodes of unique values from_ `1` _to_ `n`. Return the answer in **any order**.

**Example 1:**

**Input:** n = 3
**Output:** \[\[1,null,2,null,3\],\[1,null,3,2\],\[2,1,3\],\[3,1,null,null,2\],\[3,2,null,1\]\]

**Example 2:**

**Input:** n = 1
**Output:** \[\[1\]\]

**Constraints:**

*   `1 <= n <= 8`
Unique Binary Search Trees

Given an integer `n`, return _the number of structurally unique **BST'**s (binary search trees) which has exactly_ `n` _nodes of unique values from_ `1` _to_ `n`.

**Example 1:**

**Input:** n = 3
**Output:** 5

**Example 2:**

**Input:** n = 1
**Output:** 1

**Constraints:**

*   `1 <= n <= 19`
Interleaving String

Given strings `s1`, `s2`, and `s3`, find whether `s3` is formed by an **interleaving** of `s1` and `s2`.

An **interleaving** of two strings `s` and `t` is a configuration where `s` and `t` are divided into `n` and `m` substrings respectively, such that:

*   `s = s1 + s2 + ... + sn`
*   `t = t1 + t2 + ... + tm`
*   `|n - m| <= 1`
*   The **interleaving** is `s1 + t1 + s2 + t2 + s3 + t3 + ...` or `t1 + s1 + t2 + s2 + t3 + s3 + ...`

**Note:** `a + b` is the concatenation of strings `a` and `b`.

**Example 1:**

**Input:** s1 =  "aabcc ", s2 =  "dbbca ", s3 =  "aadbbcbcac "
**Output:** true
**Explanation:** One way to obtain s3 is:
Split s1 into s1 =  "aa " +  "bc " +  "c ", and s2 into s2 =  "dbbc " +  "a ".
Interleaving the two splits, we get  "aa " +  "dbbc " +  "bc " +  "a " +  "c " =  "aadbbcbcac ".
Since s3 can be obtained by interleaving s1 and s2, we return true.

**Example 2:**

**Input:** s1 =  "aabcc ", s2 =  "dbbca ", s3 =  "aadbbbaccc "
**Output:** false
**Explanation:** Notice how it is impossible to interleave s2 with any other string to obtain s3.

**Example 3:**

**Input:** s1 =  " ", s2 =  " ", s3 =  " "
**Output:** true

**Constraints:**

*   `0 <= s1.length, s2.length <= 100`
*   `0 <= s3.length <= 200`
*   `s1`, `s2`, and `s3` consist of lowercase English letters.

**Follow up:** Could you solve it using only `O(s2.length)` additional memory space?
Validate Binary Search Tree

Given the `root` of a binary tree, _determine if it is a valid binary search tree (BST)_.

A **valid BST** is defined as follows:

*   The left subtree of a node contains only nodes with keys **less than** the node's key.
*   The right subtree of a node contains only nodes with keys **greater than** the node's key.
*   Both the left and right subtrees must also be binary search trees.

**Example 1:**

**Input:** root = \[2,1,3\]
**Output:** true

**Example 2:**

**Input:** root = \[5,1,4,null,null,3,6\]
**Output:** false
**Explanation:** The root node's value is 5 but its right child's value is 4.

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 104]`.
*   `-231 <= Node.val <= 231 - 1`
Recover Binary Search Tree

You are given the `root` of a binary search tree (BST), where the values of **exactly** two nodes of the tree were swapped by mistake. _Recover the tree without changing its structure_.

**Example 1:**

**Input:** root = \[1,3,null,null,2\]
**Output:** \[3,1,null,null,2\]
**Explanation:** 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

**Example 2:**

**Input:** root = \[3,1,4,null,null,2\]
**Output:** \[2,1,4,null,null,3\]
**Explanation:** 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.

**Constraints:**

*   The number of nodes in the tree is in the range `[2, 1000]`.
*   `-231 <= Node.val <= 231 - 1`

**Follow up:** A solution using `O(n)` space is pretty straight-forward. Could you devise a constant `O(1)` space solution?
Same Tree

Given the roots of two binary trees `p` and `q`, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

**Example 1:**

**Input:** p = \[1,2,3\], q = \[1,2,3\]
**Output:** true

**Example 2:**

**Input:** p = \[1,2\], q = \[1,null,2\]
**Output:** false

**Example 3:**

**Input:** p = \[1,2,1\], q = \[1,1,2\]
**Output:** false

**Constraints:**

*   The number of nodes in both trees is in the range `[0, 100]`.
*   `-104 <= Node.val <= 104`
Symmetric Tree

Given the `root` of a binary tree, _check whether it is a mirror of itself_ (i.e., symmetric around its center).

**Example 1:**

**Input:** root = \[1,2,2,3,4,4,3\]
**Output:** true

**Example 2:**

**Input:** root = \[1,2,2,null,3,null,3\]
**Output:** false

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 1000]`.
*   `-100 <= Node.val <= 100`

**Follow up:** Could you solve it both recursively and iteratively?
Binary Tree Level Order Traversal

Given the `root` of a binary tree, return _the level order traversal of its nodes' values_. (i.e., from left to right, level by level).

**Example 1:**

**Input:** root = \[3,9,20,null,null,15,7\]
**Output:** \[\[3\],\[9,20\],\[15,7\]\]

**Example 2:**

**Input:** root = \[1\]
**Output:** \[\[1\]\]

**Example 3:**

**Input:** root = \[\]
**Output:** \[\]

**Constraints:**

*   The number of nodes in the tree is in the range `[0, 2000]`.
*   `-1000 <= Node.val <= 1000`
Binary Tree Zigzag Level Order Traversal

Given the `root` of a binary tree, return _the zigzag level order traversal of its nodes' values_. (i.e., from left to right, then right to left for the next level and alternate between).

**Example 1:**

**Input:** root = \[3,9,20,null,null,15,7\]
**Output:** \[\[3\],\[20,9\],\[15,7\]\]

**Example 2:**

**Input:** root = \[1\]
**Output:** \[\[1\]\]

**Example 3:**

**Input:** root = \[\]
**Output:** \[\]

**Constraints:**

*   The number of nodes in the tree is in the range `[0, 2000]`.
*   `-100 <= Node.val <= 100`
Maximum Depth of Binary Tree

Given the `root` of a binary tree, return _its maximum depth_.

A binary tree's **maximum depth** is the number of nodes along the longest path from the root node down to the farthest leaf node.

**Example 1:**

**Input:** root = \[3,9,20,null,null,15,7\]
**Output:** 3

**Example 2:**

**Input:** root = \[1,null,2\]
**Output:** 2

**Constraints:**

*   The number of nodes in the tree is in the range `[0, 104]`.
*   `-100 <= Node.val <= 100`
Construct Binary Tree from Preorder and Inorder Traversal

Given two integer arrays `preorder` and `inorder` where `preorder` is the preorder traversal of a binary tree and `inorder` is the inorder traversal of the same tree, construct and return _the binary tree_.

**Example 1:**

**Input:** preorder = \[3,9,20,15,7\], inorder = \[9,3,15,20,7\]
**Output:** \[3,9,20,null,null,15,7\]

**Example 2:**

**Input:** preorder = \[-1\], inorder = \[-1\]
**Output:** \[-1\]

**Constraints:**

*   `1 <= preorder.length <= 3000`
*   `inorder.length == preorder.length`
*   `-3000 <= preorder[i], inorder[i] <= 3000`
*   `preorder` and `inorder` consist of **unique** values.
*   Each value of `inorder` also appears in `preorder`.
*   `preorder` is **guaranteed** to be the preorder traversal of the tree.
*   `inorder` is **guaranteed** to be the inorder traversal of the tree.
Construct Binary Tree from Inorder and Postorder Traversal

Given two integer arrays `inorder` and `postorder` where `inorder` is the inorder traversal of a binary tree and `postorder` is the postorder traversal of the same tree, construct and return _the binary tree_.

**Example 1:**

**Input:** inorder = \[9,3,15,20,7\], postorder = \[9,15,7,20,3\]
**Output:** \[3,9,20,null,null,15,7\]

**Example 2:**

**Input:** inorder = \[-1\], postorder = \[-1\]
**Output:** \[-1\]

**Constraints:**

*   `1 <= inorder.length <= 3000`
*   `postorder.length == inorder.length`
*   `-3000 <= inorder[i], postorder[i] <= 3000`
*   `inorder` and `postorder` consist of **unique** values.
*   Each value of `postorder` also appears in `inorder`.
*   `inorder` is **guaranteed** to be the inorder traversal of the tree.
*   `postorder` is **guaranteed** to be the postorder traversal of the tree.
Binary Tree Level Order Traversal II

Given the `root` of a binary tree, return _the bottom-up level order traversal of its nodes' values_. (i.e., from left to right, level by level from leaf to root).

**Example 1:**

**Input:** root = \[3,9,20,null,null,15,7\]
**Output:** \[\[15,7\],\[9,20\],\[3\]\]

**Example 2:**

**Input:** root = \[1\]
**Output:** \[\[1\]\]

**Example 3:**

**Input:** root = \[\]
**Output:** \[\]

**Constraints:**

*   The number of nodes in the tree is in the range `[0, 2000]`.
*   `-1000 <= Node.val <= 1000`
Convert Sorted Array to Binary Search Tree

Given an integer array `nums` where the elements are sorted in **ascending order**, convert _it to a_ **_height-balanced_** _binary search tree_.

**Example 1:**

**Input:** nums = \[-10,-3,0,5,9\]
**Output:** \[0,-3,9,-10,null,5\]
**Explanation:** \[0,-10,5,null,-3,null,9\] is also accepted:
 

**Example 2:**

**Input:** nums = \[1,3\]
**Output:** \[3,1\]
**Explanation:** \[1,null,3\] and \[3,1\] are both height-balanced BSTs.

**Constraints:**

*   `1 <= nums.length <= 104`
*   `-104 <= nums[i] <= 104`
*   `nums` is sorted in a **strictly increasing** order.