展平二叉搜索树-递归

孙泽辉

发布于：2021年9月1日

字数：643字

时长：2分钟

次浏览

找点题做做。。

剑指 Offer II 052. 展平二叉搜索树

难度 简单

给你一棵二叉搜索树，请 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

示例 1：

输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

示例 2：

输入：root = [5,1,7]
输出：[1,null,5,null,7]

题解

输出看起来很规矩，直接排个序堆起来就好了嘛。。

不行我要练习二叉树，最终用书上的知识点：

那就中序遍历一下把元素排好序，再把元素往右子树上挂就好了。

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

// 中序遍历
function midOrder(
  res: Array<TreeNode>,
  root: TreeNode | null
): TreeNode | null {
  if (!root) return null;

  midOrder(res, root.left);
  res.push(root);
  midOrder(res, root.right);
}

function increasingBST(root: TreeNode | null): TreeNode | null {
  const midO: Array<TreeNode> = [];
  midOrder(midO, root);
  const tree = new TreeNode();
  let t = tree;
  // 将元素挂到右子树上
  while (midO.length) {
    t.right = new TreeNode(midO.shift().val);
    t = t.right;
  }
  return tree.right;
}

总结

学了二叉搜索树之后感觉跟二分查找有点不相上下的意思，他们之间的区别如下，

从查找过程看，二叉排序树与二分查找相似。
就平均时间性能。二叉排序树上的查找和二分查找差不多。但二分查找判定树唯一，而二叉排序树的查找不唯一，相同的关键字其插入顺序不同可能生成不同的二叉排序树。
维护表的有序性。二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，二分查找的对象是有序顺序表插入和删除节点的操作所花代价。
静态查找表时，选择二分查找。动态查找表时，选择二叉排序树。
————————————————
版权声明：本文为CSDN博主「一北_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/black_procedure/article/details/109133449

题目地址：

展平二叉搜索树