0701. Insert into a Binary Search Tree

题目信息

题号:

0701

难度:

Medium

主题:

二叉搜索树、节点插入、树结构

原题:

LeetCode 0701

重点:

输入可能为空树,待插入值原本不存在;返回加入新节点后的 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]
解释:原树没有节点,因此新节点成为结果树的根节点。