Contents

# 701. Insert into a Binary Search Tree

## 題目 :

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

• Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

### Example :

Note

Example 1:

Input: root = [4,2,7,1,3], val = 5 Output: [4,2,7,1,3,5] Explanation: Another accepted tree is:

Example 2:

Input: root = [40,20,60,10,30,50,70], val = 25 Output: [40,20,60,10,30,50,70,null,null,25]

Example 3:

Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5 Output: [4,2,7,1,3,5]

#### 解題思路 :

• 這題跟 leetcode235概念是一樣的，本身insert也就是search到合理位置後插入

• 這題提供了兩個寫法，兩個概念是一樣的，只是寫法差一些而已，第一個是我照著自己直觀的想法第一次寫的，我把insert的功能寫在另一個function，並將邏輯切得比較細，第二個更高明的利用recursive跟值的回溯，可以好好的研究一下

### Recursive解法-1

• time complexity: O(log(n)) , space complexity: O(1)

Runtime: 22 ms, faster than 94.32% of Go online submissions for Insert into a Binary Search Tree.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 `````` ``````/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func insertIntoBST(root *TreeNode, val int) *TreeNode { newNode := &TreeNode{ Val : val, } if root == nil { return newNode } Insert(root, newNode) return root } func Insert(root *TreeNode, node *TreeNode) { if root.Val > node.Val { if root.Left != nil { Insert(root.Left, node) }else { root.Left = node return } }else { if root.Right != nil { Insert(root.Right, node) }else { root.Right = node return } } } ``````

### Recursive解法-2

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 `````` ``````/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func insertIntoBST(root *TreeNode, val int) *TreeNode { if root == nil { return &TreeNode{Val: val} } if root.Val > val { root.Left = insertIntoBST(root.Left, val) } else if root.Val < val { root.Right = insertIntoBST(root.Right, val) } return root } ``````