Print BST Kth level alternatively - Google Intreview


http://www.1point3acres.com/bbs/thread-198684-1-1.html
第一轮: Print BST Kth level alternatively比如  5 ,k = 2的话, 打印结果1 8 3 6
    /  \
   2    7
  / \  / \
  1 3 6  8
比如  5 ,k = 2的话, 打印结果3 8 6
    /  \
   2    7
    \  / \-google 1point3acres
    3 6  8

第一题从空间complexity来说确实是他的小。stack就是前序遍历非递归算法那个stack,栈内元素照理说是不超过树的高度的k。但是BFS需要维护每层所有元素,空间上是2^k。
另外对DFS来说假设树是BST是有意义的。因为两个指针有可能会相互错过对方。BST可以用来判断终止条件(左指针指向的元素<右指针)。

第一题用dfs的话space complexity只有O(k)
第一轮确实是应该双向DFS,我当时把自己绕晕了


private boolean initializeStack(TreeNode root, Stack<TreeNode> stack, int k, boolean isLeft){
    stack.push(root);
    if(stack.size() == k) return true;. Waral 鍗氬鏈夋洿澶氭枃绔�,
    if(isLeft){
    if(root.left !=null){
    if(initializeStack(root.left, stack, k, isLeft)) return true;
}
if(root.right != null){
    if(initializeStack(root.right, stack, k, isLeft)) return true;
}
}else{
if(root.right != null){
    if(initializeStack(root.right, stack, k, isLeft)) return true;
}. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
    if(root.left !=null){
    if(initializeStack(root.left, stack, k, isLeft)) return true;
}
}-google 1point3acres
stack.pop();. 1point3acres.com/bbs
return false;
}


int nextNode(Stack<TreeNode> stack, int k, boolean isLeft){
    int ans = stack.peek().val;
    TreeNode here = stack.pop();
    if(isLeft){
        while(!stack.isEmpty() && ((here == stack.peek().left && stack.peek().right == null) || here == stack.peek().right)){
            here = stack.pop();
}
if(stack.isEmpty()) return ans;. 1point3acres.com/bbs
initializeStack(stack.peek().right, stack, k, isLeft);
}else{. from: 1point3acres.com/bbs 
    while(!stack.isEmpty() && ((here == stack.peek().right && stack.peek().left == null) || here == stack.peek().left)){
    here = stack.pop();
}
if(stack.isEmpty()) return ans;
initializeStack(stack.peek().left, stack, k, isLeft);
}
return ans;
}


    public List<Integer> kthLevel(TreeNode root, int k){
        Stack<TreeNode> leftStack = new Stack<>();
        Stack<TreeNode> rightStack = new Stack<>();
        if(root == null) return new LinkedList<>();
        initializeStack(root, leftStack, k, true);
        initializeStack(root, rightStack, k, false);
        List<Integer> ans = new LinkedList<>();
while(true){
    int left = nextNode(leftStack, k, true);
    int right = nextNode(rightStack, k , false);
    if(left == right){. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
    ans.add(left); return ans;
}else if(left < right){
    ans.add(left); ans.add(right);
}else{
    return ans;
}
}
}

这道题虽然说是BST,但跟BST没啥关系。. From 1point 3acres bbs
一开始我没有很好的思路,然后面试官提示DFS/BFS,我就想到BFS+deque的做法:
  1. void printBSTKthLevelAlt(TreeNode *root, int k) {
  2.   if (root == nullptr || k < 0) {
  3.     return;
  4.   }
  5.   deque<TreeNode*> q;. 鍥磋鎴戜滑@1point 3 acres
  6.   int level = 0;
  7.   q.push_back(root);
  8.   while(!q.empty()) {
  9.     if (level == k) {
  10.       printLevel(q);
  11.       return;
  12.     }
  13.     auto ls = q.size();
  14.     for(auto i = 0; i < ls; ++i) {
  15.       auto node = q.front();
  16.       q.pop_front();
  17.       if (q->left != nullptr) {
  18.         q.push_back(q->left);
  19.       }
  20.       if (q->right != nullptr) {
  21.         q.push_back(q->right);
  22.       }
  23.     }
  24.     ++k;. 1point3acres.com/bbs
  25.   }
  26. }

  27. void printLevel(const deque<TreeNode*>& q) {
  28.   bool left = true;
  29.   while (!q.empty()) {
  30.     TreeNode* node;
  31.     if (left) {
  32.       node = q.front();
  33.       q.pop_front();
  34.     }
  35.     else {. From 1point 3acres bbs
  36.       node = q.back();
  37.       q.pop_back();
  38.     }. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
  39.     cout << node->val << ' ';
  40.     left != left;
  41.   }
  42.   cout << endl;
  43. }
然后面试官问我time&space complexity是什么,我答道O(n), O(2^k)。
然后他说怎么可以在保持time complexity的同时优化space。我就开始纠结了。. 鍥磋鎴戜滑@1point 3 acres
他提示说用DFS,我比划了半天也没想出来。然后时间快到的时候,他告诉了我他的思路:
维护两个stack,一个stack先push right child,另一个先push left child
比如我们有      a1                        这棵树,我们想打印k=3这层,
                 /            \
        a2             a3
          /    \        /      \
     a4    a5      a6      a7
    / \   /  \   /   \    /  \
   a8 a9 a10 a11 a12 a13 a14 a15

k = 1
s1: a1/a3/a2
s2: a1/a2/a3
k = 2
s1: a1/a3/a2/a5/a4
s2: a1/a2/a3/a6/a7. 鍥磋鎴戜滑@1point 3 acres
k = 3
s1: a1/a3/a2/a5/a4/a9/a8
s2: a1/a2/a3/a6/a7/a14/a15
print: a8 a15 a9 a14
k = 2
s1: a1/a3/a2/a5
s2: a1/a2/a3/a6
k = 3. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
s1: a1/a3/a2/a5/a11/a10. 1point3acres.com/bbs
s2: a1/a2/a3/a6/a12/a13
print: a10 a13 a11 a12
finish
这个思路确实比我的巧妙,但先不说这个思路写作代码会很繁琐,我就没明白这样怎么更节省空间了。
因为使用了两个stack,对空间的占用应该是半斤八两的。而且在
k = 3
s1: a1/a3/a2/a5/a4/a9/a8
s2: a1/a2/a3/a6/a7/a14/a15
这个时候,至少存了10个节点,如果用BFS的做法只会存8个节点。

  1. struct TreeNode {. Waral 鍗氬鏈夋洿澶氭枃绔�,
  2.     int val;
  3.     TreeNode* left, * right;. Waral 鍗氬鏈夋洿澶氭枃绔�,
  4.     TreeNode(int v) : val(v), left(NULL), right(NULL) {};
  5. };

  6. class TreeIterator {
  7. public:
  8.         TreeIterator(TreeNode* root, int k) : max_level(k) {. visit 1point3acres.com for more.
  9.                 if (root) stk.push(make_pair(0, root));
  10.         }
  11.         
  12.         bool has_next() { return !stk.empty(); }
  13.         
  14.         int next() {
  15.                 if (stk.empty()) throw "out of range";  .鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
  16.                 int ret_val = stk.top().second->val;
  17.                 stk.pop();
  18.                 traverse();
  19.                 return ret_val;
  20.         };        
  21.         .鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
  22.         virtual TreeNode* get_left (TreeNode *n)=0;
  23.         virtual TreeNode* get_right(TreeNode *n)=0;

  24. protected:        . 1point3acres.com/bbs
  25.         void traverse() {
  26.                 while (!stk.empty() && stk.top().first != max_level) {. 鍥磋鎴戜滑@1point 3 acres
  27.                         int next_level = stk.top().first+1;
  28.                         TreeNode* left  = get_left (stk.top().second);
  29.                         TreeNode* right = get_right(stk.top().second);
  30.                         stk.pop();
  31.                         if (right) stk.push(make_pair(next_level, right));
  32.                         if (left)  stk.push(make_pair(next_level, left ));
  33.                 }                
  34.         }
  35.         stack<pair<int, TreeNode*>> stk;
  36.         int max_level;
  37.         
  38. };

  39. class TreeForwardIterator : public TreeIterator {. Waral 鍗氬鏈夋洿澶氭枃绔�,
  40. public:
  41.     TreeForwardIterator(TreeNode* root, int k) : TreeIterator(root, k) { traverse(); };
  42.         TreeNode* get_left (TreeNode* n) { return n->left;  };. 鍥磋鎴戜滑@1point 3 acres
  43.         TreeNode* get_right(TreeNode* n) { return n->right; };
  44. };


  45. class TreeReverseIterator : public TreeIterator {-google 1point3acres
  46. public:. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
  47.     TreeReverseIterator(TreeNode* root, int k) : TreeIterator(root, k) { traverse(); };
  48.         TreeNode* get_left (TreeNode* n) { return n->right; };
  49.     TreeNode* get_right(TreeNode* n) { return n->left;  };        
  50. };

  51. vector<int> tree_level_alt(TreeNode *root, int k) {. 1point3acres.com/bbs
  52.         TreeForwardIterator i_left (root, k);
  53.         TreeReverseIterator i_right(root, k);
  54.         vector<int> result;
  55.         . 1point 3acres 璁哄潧
  56.         int l = INT_MIN, r = INT_MAX;. more info on 1point3acres.com
  57.         while (l < r){
  58.                 l = i_left.has_next()  ? i_left.next()  : INT_MAX;
  59.                 r = i_right.has_next() ? i_right.next() : INT_MIN;
  60.                 if (l < r) { result.push_back(l); result.push_back(r);}
  61.                 else { if (l == r) result.push_back(l); }. 1point3acres.com/bbs
  62.         }
  63.         return result;
  64. };

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts