[Day25]-[二叉树] 二叉搜索树中的插入操作

2022 年 4 月 25 日
本文字数：621 字
阅读完需：约 2 分钟

701. 二叉搜索树中的插入操作

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

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

示例 1：

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

复制代码

示例 2：

输入：root = [40,20,60,10,30,50,70], val = 25输出：[40,20,60,10,30,50,70,null,null,25]

复制代码

示例 3：

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

复制代码

题解：

func TestInsertIntoBST(t *testing.T) {	root := &TreeNode{		Val: 2,		Left: &TreeNode{			Val: 1,		},		Right: &TreeNode{			Val: 3,		},	}	var insertIntoBST func(root *TreeNode, val int) *TreeNode	insertIntoBST = func(root *TreeNode, val int) *TreeNode {		if root == nil {			return &TreeNode{				Val: val,			}		}		// 先递推 再 回归		// 4>2 => 2.Right = insertIntoBST(3,4)		// 4>3 => 3.Right = insertIntoBST(nil,4)		// 再回归 2.Right = 3带上了4		if val > root.Val {			root.Right = insertIntoBST(root.Right, val)		} else {			root.Left = insertIntoBST(root.Left, val)		}		return root	}
	t.Log(insertIntoBST(root, 4))}

复制代码

发布于: 11 小时前阅读数: 2

方勇(gopher)

关注

Dead or Alive. 生存战斗是知识的源泉！ 2018.11.08 加入

我是一名SRE哨兵，目前是好大夫基础架构部高级工程师。专注于 SRE，微服务、中间件的稳定性和可用性建设，整体负责好大夫服务治理云平台的设计和搭建！

发布

暂无评论

创作场景

[Day25]-[二叉树] 二叉搜索树中的插入操作

701. 二叉搜索树中的插入操作

方勇(gopher)

评论