Contents

[Golang][Leetcode][BinaryTree]刷題系列-700-Search in a Binary Search Tree


700. Search in a Binary Search Tree


Level : Easy

原題連結 : Click

題目 :

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return null.


Example :

Note

Example 1:

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

Example 2:

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


解題思路 :

  • 這題非常簡單,只是要考察你知不知道BST(Binary Search Tree)是什麼!
  • Definition of BST : 一個binary tree 由一個root,一個left subtree和一個right subtree組成,其中left subtree中所有的node都小於它的root,而它的right subtree中所有的node都大於它的root,然後每一個subtree都符合BST。

Recursive解法

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

Runtime: 20 ms, faster than 93.06% of Go online submissions for Search in 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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func searchBST(root *TreeNode, val int) *TreeNode {
    
    if root == nil {
        return nil
    }
    
    if root.Val == val {
        
        return root
        
    }else if root.Val > val {
        
        return searchBST(root.Left, val)
        
    }
        
    return searchBST(root.Right, val)    
}

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