跳至主要內容
109, 将有序列表转换为二叉搜索树

一、题目描述

给定一个单链表的头节点head,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差不超过1

示例 1

输入: head = [-10, -3, 0, 5, 9]
输出: [0, -3, 9, -10, null, 5]
解释: 一个可能的答案是[0,-3, 9,-10, null, 5],它表示所示的高度平衡的二叉搜索树。


Mike大约 3 分钟binary treemediumlinked listbinary treebinary search treedivide and conquer
108, 将有序数组转换为二叉搜索树

一、题目描述

给你一个整数数组nums,其中元素已经按升序排列,请你将其转换为一棵高度平衡二叉搜索树。

高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过1」的二叉树。

示例 1

输入: nums = [-10, -3, 0, 5, 9]
输出: [0, -3, 9, -10, null, 5]
解释: [0, -10, 5, null, -3, null, 9] 也将被视为正确答案:


Mike大约 3 分钟binary treeeasytreebinary treebinary search treearraydivide and conquer
669, 修剪二叉搜索树

一、题目描述

给你二叉搜索树的根节点root,同时给定最小边界low和最大边界high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。可以证明,存在唯一的答案

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意,根节点可能会根据给定的边界发生改变。

示例 1

输入: root = [1, 0, 2], low = 1, high = 2
输出: [1, null, 2]


Mike大约 2 分钟binary treemediumbinary treebinary search treedepth first search
450, 删除二叉搜索树中的节点

一、题目描述

给定一个二叉搜索树的根节点root和一个值key,删除二叉搜索树中的key对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

一般来说,删除节点可分为两个步骤:

  1. 首先找到需要删除的节点;
  2. 如果找到了,删除它。

示例 1

输入: root = [5, 3, 6, 2, 4, null, 7], key = 3
输出: [5, 4, 6, 2, null, null, 7]
解释: 给定需要删除的节点值是3,所以我们首先找到3这个节点,然后删除它。


Mike大约 3 分钟binary treemediumbinary treebinary search tree
701, 二叉搜索树中的插入操作

一、题目描述

给定二叉搜索树(BST)的根节点root和要插入树中的值value,将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证新值和原始二叉搜索树中的任意节点值都不同。

注意:可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果

示例 1

输入: root = [4, 2, 7, 1, 3], val = 5
输出: [4, 2, 7, 1, 3, 5]
解释: 另一个满足题目要求可以通过的树是:


Mike大约 3 分钟binary treemediumbinary treebinary search tree
235, 二叉搜索树的最近公共祖先

一、题目描述

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:"对于有根树T的两个结点pq,最近公共祖先表示为一个结点x,满足xpq的祖先且x的深度尽可能大(一个节点也可以是它自己的祖先)。"


Mike大约 4 分钟binary treemediumtreebinary treebinary search treedepth first search
538, 把二叉搜索树转换为累加树

一、题目描述

给出二叉搜索树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点node的新值等于原树中大于或等于node.val的值之和。

提醒一下,二叉搜索树满足下列约束条件:

  • 节点的左子树仅包含键小于节点键的节点。
  • 节点的右子树仅包含键大于节点键的节点。
  • 左右子树也必须是二叉搜索树。

Mike大约 3 分钟binary treemediumbinary treedepth first searchbinary search tree
501, 二叉搜索树中的众数

一、题目描述

给你一个含重复值的二叉搜索树(BST)的根节点root,找出并返回BST中的所有众数(即出现频率最高的元素)。

如果树中有不止一个众数,可以按任意顺序返回。

假定BST满足如下定义:


Mike大约 6 分钟binary treeeasybinary treedepth first searchbinary search tree
530, 二叉搜索树的最小绝对差

一、题目描述

给你一个二叉搜索树的根节点root,返回树中任意两个不同节点值之间的最小差值

差值是一个正数,其数值等于两值之差的绝对值。

示例 1

输入: root = [4, 2, 6, 1, 3]
输出: 1

示例 2

输入: root = [1, 0, 48, null, null, 12, 49]
输出: 1

提示


Mike大约 2 分钟binary treeeasybinary treebinary search treedepth first searchbreadth first search
98, 验证二叉搜索树

一、题目描述

给你一个二叉树的根节点root,判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下:

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1

输入: root = [2, 1, 3]
输出: true


Mike大约 4 分钟binary treemediumbinary treedepth first searchbinary search tree
2