Categorygithub.com/szhou12/leetcode-goleetcode0700-Search-in-a-Binary-Search-Tree
package
0.0.0-20241220224003-b7cf03a90b2b
Repository: https://github.com/szhou12/leetcode-go.git
Documentation: pkg.go.dev
Overview
Dependencies
1
Dependents
0

# README

700. Search in a Binary Search Tree

Solution idea

  • 又是一道Binary Search Tree的题，明示了要利用BST性质解题

  • 如何利用BST性质？

    • 当遇到空节点, 说明要找的节点tree里没有, 返回空
    • 当前节点就是要找的, 返回当前节点
    • 如果当前节点的值 > target value: 目标节点只可能出现在左子树 (根据BST性质, 右子树都 > target)
    • 如果当前节点的值 < target value: 目标节点只可能出现在右子树 (根据BST性质, 左子树都 < target)

Time complexity = $O(\log n)$ because every recursion only traveres half of tree