0701. Insert into a Binary Search Tree¶
题目信息¶
- 题号:
0701
- 难度:
Medium
- 主题:
二叉搜索树、节点插入、树结构
- 原题:
- 重点:
输入可能为空树,待插入值原本不存在;返回加入新节点后的 BST 根节点,存在多种合法结构时任意一种均可
题目重述¶
给定一棵二叉搜索树的根节点 root 和一个整数 val。树中所有已有节点值互不相同,并且 val 不在原树中。请向树中加入一个值为 val 的新节点,使结果仍满足二叉搜索树性质,并返回结果树的根节点。
原树可以为空。插入后必须保留原有全部节点及其值;若有多种结构都满足二叉搜索树性质,可以返回其中任意一种。树中原有节点数在 [0, 10^4] 范围内,节点值与 val 均在 [-10^8, 10^8] 范围内。
自建示例¶
插入到内部节点下方:
输入:root = [8,3,12,1,6,10,14], val = 5
输出:[8,3,12,1,6,10,14,null,null,5]
解释:新增值 5 小于 8、大于 3 且小于 6,把它作为节点 6 的左孩子后,整棵树仍满足二叉搜索树性质。其他合法结构也可以接受。
向空树插入:
输入:root = [], val = -4
输出:[-4]
解释:原树没有节点,因此新节点成为结果树的根节点。