590.n-叉树的后序遍历.md

590.n-叉树的后序遍历

/*
 * @lc app=leetcode.cn id=590 lang=typescript
 *
 * [590] N 叉树的后序遍历
 */

// @lc code=start
/**
 * Definition for node.
 * class Node {
 *     val: number
 *     children: Node[]
 *     constructor(val?: number) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.children = []
 *     }
 * }
 */

interface Node {
  val: number
  children: Node[]
}
function postorder(root: Node | null): number[] {}
// @lc code=end

解法 1: 递归

• 时间复杂度:
• 空间复杂度:

function postorder(root: Node | null): number[] {
  if (!root) return []
  return root.children.reduce<number[]>((nums, node) => nums.concat(postorder(node)), []).concat(root.val)
}

解法 2: 迭代

• 时间复杂度:
• 空间复杂度:

function postorder(root: Node | null): number[] {
  if (!root) return []

  const stack: Array<Node> = [root]
  const result: Array<number> = []
  while (stack.length) {
    const node = stack.pop()!
    result.push(node.val)
    for (let i = 0; i < node.children.length; i++) {
      const tmp = node.children[i]
      stack.push(tmp)
    }
  }
  return result.reverse()
}

解法 3: 递归 2

• 时间复杂度:
• 空间复杂度:

function postorder(root: Node | null, res: number[] = []): number[] {
  if (!root) return res
  for (const child of root.children) postorder(child, res)
  res.push(root.val)
  return res
}

Case

test.each([
  { input: '[1,null,3,2,4,null,5,6]', output: [5, 6, 3, 2, 4, 1] },
  {
    input: '[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],
  },
])('root = $result', ({ input, output }) => {
  const root = NaryTree.deserialize(input)
  expect(postorder(root)).toEqual(output)
})