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

二叉搜索树中的插入操作

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

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

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

思路

可以不考虑题目中提示所说的改变树的结构的插入方式

只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了

代码

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil { // 找到空节点 插入val节点后返回
        root = &TreeNode{Val: val}
        return root
    }
    if root.Val > val {
        root.Left = insertIntoBST(root.Left, val) // val<root 向左搜索
    } else {
        root.Right = insertIntoBST(root.Right, val) // val>root 向右搜索
    }
    return root
}

Link

GitHub