面试题17.12.BiNode

链接：面试题17.12.BiNode
难度：Easy
标签：栈、树、深度优先搜索、二叉搜索树、链表、二叉树
简介：二叉树数据结构 TreeNode 可用来表示单向链表（其中 left 置空，right 为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。返回转换后的单向链表的头节点。

题解 1 - typescript

• 编辑时间：2021-08-07
• 执行用时：120ms
• 内存消耗：53.6MB
• 编程语言：typescript
• 解法介绍：中序遍历。

function convertBiNode(root: TreeNode | null): TreeNode | null {
  if (root === null) return null;
  const q: TreeNode[] = [];
  inorder(root);
  for (let i = 0; i < q.length - 1; i++) {
    q[i].left = null;
    q[i].right = q[i + 1];
  }
  q[q.length - 1].left = q[q.length - 1].right = null;
  return q[0];
  function inorder(node: TreeNode | null): void {
    if (node === null) return;
    inorder(node.left);
    q.push(node);
    inorder(node.right);
  }
}