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

2021-09-12 395 words 2 minutes

/leetcode701_binarytree/golang_leetcode.png

Contents

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” 我們峰頂見!!!