897.递增顺序搜索树

链接：897.递增顺序搜索树
难度：Easy
标签：栈、树、深度优先搜索、二叉搜索树、二叉树
简介：给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

题解 1 - typescript

• 编辑时间：2021-04-25
• 执行用时：88ms
• 内存消耗：39.7MB
• 编程语言：typescript
• 解法介绍：递归遍历每个点。

function increasingBST(root: TreeNode | null): TreeNode | null {
  function increasing(node: TreeNode): [TreeNode, TreeNode] {
    if (!root.left && !root.right) return [root, root];
    let first = node;
    let last = node;
    if (node.left !== null) {
      const data = increasing(node.left);
      first = data[0];
      data[1].right = node;
      node.left = null;
    }
    if (node.right !== null) {
      const data = increasing(node.right);
      last.right = data[0];
      last = data[1];
    }
    return [first, last];
  }
  return increasing(root)[0];
}

题解 2 - typescript

• 编辑时间：2021-04-25
• 执行用时：132ms
• 内存消耗：40.2MB
• 编程语言：typescript
• 解法介绍：先中序遍历后逐个赋值。

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