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