Massive Algorithms: Print BST Kth level alternatively

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
\  / \
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;
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;
}
}
stack.pop();
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;
initializeStack(stack.peek().right, stack, k, isLeft);
}else{
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没啥关系。
一开始我没有很好的思路，然后面试官提示DFS/BFS，我就想到BFS+deque的做法：

void printBSTKthLevelAlt(TreeNode *root, int k) {
if (root == nullptr || k < 0) {
return;
}
deque<TreeNode*> q;. 鍥磋鎴戜滑@1point 3 acres
int level = 0;
q.push_back(root);
while(!q.empty()) {
if (level == k) {
printLevel(q);
return;
}
auto ls = q.size();
for(auto i = 0; i < ls; ++i) {
auto node = q.front();
q.pop_front();
if (q->left != nullptr) {
q.push_back(q->left);
}
if (q->right != nullptr) {
q.push_back(q->right);
}
}
++k;. 1point3acres.com/bbs
}
}
void printLevel(const deque<TreeNode*>& q) {
bool left = true;
while (!q.empty()) {
TreeNode* node;
if (left) {
node = q.front();
q.pop_front();
}
else {. From 1point 3acres bbs
node = q.back();
q.pop_back();
}. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
cout << node->val << ' ';
left != left;
}
cout << endl;
}

然后面试官问我time&space complexity是什么，我答道O(n), O(2^k)。
然后他说怎么可以在保持time complexity的同时优化space。我就开始纠结了。
他提示说用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
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
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个节点。

struct TreeNode {. Waral 鍗氬鏈夋洿澶氭枃绔�,
int val;
TreeNode* left, * right;. Waral 鍗氬鏈夋洿澶氭枃绔�,
TreeNode(int v) : val(v), left(NULL), right(NULL) {};
};
class TreeIterator {
public:
TreeIterator(TreeNode* root, int k) : max_level(k) {. visit 1point3acres.com for more.
if (root) stk.push(make_pair(0, root));
}
bool has_next() { return !stk.empty(); }
int next() {
if (stk.empty()) throw "out of range"; .鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
int ret_val = stk.top().second->val;
stk.pop();
traverse();
return ret_val;
};
.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
virtual TreeNode* get_left (TreeNode *n)=0;
virtual TreeNode* get_right(TreeNode *n)=0;
protected: . 1point3acres.com/bbs
void traverse() {
while (!stk.empty() && stk.top().first != max_level) {. 鍥磋鎴戜滑@1point 3 acres
int next_level = stk.top().first+1;
TreeNode* left = get_left (stk.top().second);
TreeNode* right = get_right(stk.top().second);
stk.pop();
if (right) stk.push(make_pair(next_level, right));
if (left) stk.push(make_pair(next_level, left ));
}
}
stack<pair<int, TreeNode*>> stk;
int max_level;
};
class TreeForwardIterator : public TreeIterator {. Waral 鍗氬鏈夋洿澶氭枃绔�,
public:
TreeForwardIterator(TreeNode* root, int k) : TreeIterator(root, k) { traverse(); };
TreeNode* get_left (TreeNode* n) { return n->left; };. 鍥磋鎴戜滑@1point 3 acres
TreeNode* get_right(TreeNode* n) { return n->right; };
};
class TreeReverseIterator : public TreeIterator {-google 1point3acres
public:. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
TreeReverseIterator(TreeNode* root, int k) : TreeIterator(root, k) { traverse(); };
TreeNode* get_left (TreeNode* n) { return n->right; };
TreeNode* get_right(TreeNode* n) { return n->left; };
};
vector<int> tree_level_alt(TreeNode *root, int k) {. 1point3acres.com/bbs
TreeForwardIterator i_left (root, k);
TreeReverseIterator i_right(root, k);
vector<int> result;
. 1point 3acres 璁哄潧
int l = INT_MIN, r = INT_MAX;. more info on 1point3acres.com
while (l < r){
l = i_left.has_next() ? i_left.next() : INT_MAX;
r = i_right.has_next() ? i_right.next() : INT_MIN;
if (l < r) { result.push_back(l); result.push_back(r);}
else { if (l == r) result.push_back(l); }. 1point3acres.com/bbs
}
return result;
};

Print BST Kth level alternatively - Google Intreview

Labels

Popular Posts