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/leileiluoluo/

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
}