X1_Binary Search Tree

发表于   |   分类于 ，   |     |   阅读次数

§Binary Search Tree

§Reference

Binary Search Tree | Set 1 (Search and Insertion)

Github | X1_Binary Search Tree

§Definition

  1. left subtree < root < right subtree

  2. no duplicate nodes

    • What if duplicate? add “count” attribution

    • self-balance: almost full tree. Using red-black tree

    • worst case:

    • 1
      2
      3
      4
      5
      6
      7
      1\2\3\4\5\6
      or
         1
         2
         3
         4
      5/6 7\8

  3. ​

§Coding

• https://leetcode.com/problems/find-k-closest-elements

• https://leetcode.com/problems/closest-binary-search-tree-value

• https://leetcode.com/problems/closest-binary-search-tree-value-ii

• https://leetcode.com/problems/binary-tree-level-order-traversal

• https://leetcode.com/problems/maximum-depth-of-binary-tree

• https://leetcode.com/problems/balanced-binary-tree

• https://leetcode.com/problems/search-in-rotated-sorted-array

• https://leetcode.com/problems/search-in-rotated-sorted-array-ii

####Note

  1. 先定signature

  2. 库函数Arrays.binarySearch(arr, x)，not found: < 0

  3. java8 Collectors

  4. 1
    private static final double EPSILON = 1e-10;

  5. boilerplate模版

  6. 主动测试test case

  7. 1
    Queue<T> q = new LinkedList<>();

  8. IterativeInOrder, Pre, Post

§Q

  • 360.Sort Transformed Array

    a > 0,

    binary search find the closest one with -b/2a, then …

    Or from l & r -> middle

  • 173.Binary Search Tree iterator