# Algorithm

## TIL 2021.04.28

# 942. DI String Match

A permutation `perm`

of `n + 1`

integers of all the integers in the range `[0, n]`

can be represented as a string `s`

of length `n`

where:

`s[i] == 'I'`

if`perm[i] < perm[i + 1]`

, and`s[i] == 'D'`

if`perm[i] > perm[i + 1]`

.

Given a string `s`

, reconstruct the permutation `perm`

and return it. If there are multiple valid permutations perm, return **any of them**.

**Example 1:**

**Input:** s = "IDID"

**Output:** [0,4,1,3,2]

**Example 2:**

**Input:** s = "III"

**Output:** [0,1,2,3]

**Example 3:**

**Input:** s = "DDI"

**Output:** [3,2,0,1]

**Constraints:**

`1 <= s.length <= 105`

`s[i]`

is either`'I'`

or`'D'`

.

# 590. N-ary Tree Postorder Traversal

Given the `root`

of an n-ary tree, return *the postorder traversal of its nodes' values*.

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

**Example 1:**

**Input:** root = [1,null,3,2,4,null,5,6]

**Output:** [5,6,3,2,4,1]

**Example 2:**

**Input:** root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

**Output:** [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

**Constraints:**

- The number of nodes in the tree is in the range
`[0, 104]`

. `0 <= Node.val <= 104`

- The height of the n-ary tree is less than or equal to
`1000`

.