3376-实现中序遍历

题目描述

Implement the type version of binary tree inorder traversal.

For example:

const tree1 = {
  val: 1,
  left: null,
  right: {
    val: 2,
    left: {
      val: 3,
      left: null,
      right: null,
    },
    right: null,
  },
} as const;

type A = InorderTraversal<typeof tree1>; // [1, 3, 2]

分析

尽管已经做了很多题，但是当笔者看到中序遍历的时候，心中还是大惊，这都行？

虽然看起来不可思议，但是以刷了这么多道题的思路，其实静下心来实现是并不困难的。

中序遍历，就是先取左子树，再取当前值，再取右子树。

题解

type InorderTraversal<T extends TreeNode | null> = [T] extends [TreeNode]
  ? [
      // 遍历左树
      ...InorderTraversal<T['left']>,
      T['val'],
      // 遍历右树
      ...InorderTraversal<T['right']>,
    ]
  : [];

这里值得一题的是 [T] extends [TreeNode]，为什么这么写而不是 T extends TreeNode，后者会报递归层数过深。说实话，我也没有搞的特别明白，马马虎虎可以认为是 这里 (opens new window) 的讨论，但是实际却是没看出来，隐隐约约觉得是条件判定的问题，但是确实说不出一二三。暂且搁置

知识点

1. 递归解决嵌套问题