[Golang][Leetcode][BinaryTree]刷題系列-701-Insert into a Binary Search Tree

701. Insert into a Binary Search Tree
Level : Medium
原題連結 : Click
題目 :
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 :
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.
|
|
Recursive解法-2
|
|
最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!