Contents

[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 :

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
}


最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!