LeetCode 701 二叉搜索树插入

1 题目描述

给定一个二叉搜索树(BST)的根节点及待插入值。请将该值插入到该二叉搜索树,然后返回值插入后的二叉搜索树。(注:待插入值在原二叉搜索树中不存在)

可能存在多种有效的插入方式,即只要在值插入后仍旧是二叉搜索树即可。您可以返回有效结果的任意一种。

例子:

输入:

给定树:

        4
       / \
      2   7
     / \
    1   3

及插入值:5

输出:

您可以返回如下二叉搜索树:

         4
       /   \
      2     7
     / \   /
    1   3 5

返回如下二叉搜索树也是有效的:

         5
       /   \
      2     7
     / \   
    1   3
         \
          4

题目出处:LeetCode

2 解决思路

判断插入值与根节点的大小,进而决定将该值插入到左子树还是右子树,递归调用,直至找到最终位置。

3 Golang实现代码

https://github.com/olzhy/

func insertIntoBST(root *TreeNode, val int) *TreeNode {
	if nil == root {
		return &TreeNode{Val: val}
	}

	if val > root.Val {
		root.Right = insertIntoBST(root.Right, val)
	} else {
		root.Left = insertIntoBST(root.Left, val)
	}
	return root
}
若觉得文章对您有所帮助,可以请我喝杯咖啡,Thanks!
微信 支付宝