link: https://leetcode.com/problems/two-sum-iv-input-is-a-bst/
最直觀想到的作法,先 inorder 跑一遍 BST,將元素依小至大的順序存進一個 list,那這個問題就被化簡為 Two Sum II - Input array is sorted,再搭配 two pointer 的作法,時間和空間複雜度都會是\(O(n)\)。
Accepted
Runtime: 92 ms, faster than 34.56% of Python3 online submissions for Two Sum IV - Input is a BST.
Memory Usage: 19.3 MB, less than 28.76% of Python3 online submissions for Two Sum IV - Input is a BST.
在前一題 Two Sum II - Input array is sorted 的 two pointer 作法優點是 \(O(1)\) 的空間複雜度,然而這題化簡用的 list 卻需要 \(O(n)\) 的空間複雜度,那其實也能用 Two Sum 的 hash table 作法,一旦找到答案就 return,會比前一個作法全部都找一遍還快些。
這裡用 BFS 來 traverse BST。另外,如果題目有保證 BST 是 balanced,那麼 DFS 的做法可以到 \(O(log\ n)\) 空間複雜度,因為 stack 裡面最多存放 BST height 個 node。
Accepted
Runtime: 80 ms, faster than 67.18% of Python3 online submissions for Two Sum IV - Input is a BST.
Memory Usage: 16.6 MB, less than 71.99% of Python3 online submissions for Two Sum IV - Input is a BST.
leetcode