272. Closest Binary Search Tree Value II

• 272. Closest Binary Search Tree Value II
  • Description
  • Intuition
    • PriorityQueue
    • Merge List
    • 2 Stack
  • Pitfall
  • Solution
  • Reference

Description

Here

Intuition

三种方法求解

1. PriorityQueue
2. Merge List
3. 2 Stack

PriorityQueue

遍历tree，用一个priority queue 记录diff 最小的value Solution

Time Complexity: O(N * log(K))

Merge List

遍历tree，把大于等于target的全部扔进一个queue，小于的扔进另一个，然后用merge list的方法获得最后的list

Solution

Time Complexity: O(N)

2 Stack

按照遍历tree的方法，你可以把merge list 的方法引申过来，就是把pre node要放入stack的放入一个stack中，然后post node放到另一个stack中

Time Complexity:

1. building 2 stacks cost O(log N)
2. Every time calling next*() method costs amortized O(1)

In worst case, when k = n, it costs O(n)

Solution

Pitfall

Solution

Reference

Time Complexity Analysis-Java-Solution-with-two-stacks-following-hint/72706)