面完快手，一道问题求指教

是不是要会双击666

肯定是你没有     吃灯泡，吃辣椒那种绝技，

写了一个程序，求大神看看 # -*- coding: UTF-8 -*-. class Node(object):     """节点类"""     def __init__(self, data = -1, lchild = None, rchild = None, isEmpty = 0):         self.data = data         self.lchild = lchild         self.rchild = rchild         self.isEmpty = isEmpty class BinaryTree(object):     """树类"""     def __init__(self):         self.root = Node(isEmpty = 1)     def add(self, data):         """为树增加节点，建立二叉查找树"""         node = Node(data)         if self.root.isEmpty == 1:             self.root = node         else:             treeNode = self.root             while(1):                 if node.data <= treeNode.data:                     if treeNode.lchild == None:                         treeNode.lchild = node                         break                     else:                         treeNode = treeNode.lchild                 else:                     if treeNode.rchild == None:                         treeNode.rchild = node                         break                     else:                         treeNode = treeNode.rchild     def printTree(self):         """按之字形顺序打印二叉树"""         if self.root == None:             return         myList = []         myList.append(self.root)         flagForward = 0# 为0表示下一行逆序打印，为1表示下一行正序打印         numberNow = 1         numberNext = 0         while(1):             # 表示在该行查找             if numberNow:                 # 总是将先放入的先打印出来                 node = myList.pop(0)                 numberNow -= 1                 print node.data,                 # 根据flagForward的值改变左右子树的打印数学                 if flagForward:                     if node.rchild:                         myList.insert(numberNow, node.rchild)                         numberNext += 1                     if node.lchild:                         myList.insert(numberNow, node.lchild)                         numberNext += 1                 else:                     if node.lchild:                         myList.insert(numberNow, node.lchild)                         numberNext += 1                     if node.rchild:                         myList.insert(numberNow, node.rchild)                         numberNext += 1             # 表示该行结束了             else:                 # 下一行变成该行                 if numberNext:                     numberNow = numberNext                     numberNext = 0                     # 正方向逆序                     flagForward = ~flagForward                 # 表示树结束了                 else:                     break def test():     'Test the program.'     arr = [5, 6, 1, 4, 2, 69, -1, 24]     tree = BinaryTree()     for item in arr:         tree.add(item)     #         5     #     1       6     # -1    5      69     #      2      24     print '按之字形顺序打印二叉树：'     tree.printTree() if __name__ == "__main__":     test()

面经呢？？？23333333333333

都问些啥

感觉咋样啊

你表演的啥绝活呀，兄弟？

请问快手哪里投递

队列可以反向迭代（java api）

意思是上一层和下一层的数要分开，可以用两个变量numPrevious，numNext分别记录上一层和下一层在序列中的个数，numPrevious减1的时候numNext要加上对应的子数的个数，当numPrevious为0的时候表示该行结束了，如果numNext不为0就把numNext赋给numPrevious，如果为0就表示树结束了。

之字形一个队列完成？你倒是叫面试官说说怎么做啊。反正，我是不知道一个队列要怎么打之字形。

关键一个队列不知道什么时候换向折返

用doubly linked list实现队列，一个变量存当前层traverse方向，根据方向判断存取node的方向和顺序。。。

楼主来一发面经~

#include<cstdio> #include<cstdlib> #include<cmath> #include<ctime> #include<cstring> #include<cassert> #include<climits> #include<iostream> #include<sstream> #include<vector> #include<set> #include<map> #include<stack> #include<queue> #include<bitset> #include<algorithm> #include<iterator> #include<string> #include<tuple> #include<random> #include <chrono> using namespace std; struct TreeNode {     int val;     TreeNode* left;     TreeNode* right;     TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; void zigzag(TreeNode* root) {     vector<TreeNode*> pts;     if (NULL == root)         return;     queue<TreeNode*> q;     q.push(root);     int num1 = 1, num2 = 0;     TreeNode* cur = NULL;     while (!q.empty()) {         cur = q.front();         q.pop();         if (cur->left != NULL) {             q.push(cur->left);             num2++;         }         if (cur->right != NULL) {             q.push(cur->right);             num2++;         }         pts.push_back(cur);         num1--;         if (0 == num1) {             pts.push_back(NULL);             num1 = num2;             num2 = 0;         }     }     int n = pts.size();     int rev = 0;     int i, j;     i = -1;     int mid, sum;     while (i < n) {         j = i + 1;         while (j < n && pts[j] != NULL)             j++;         // reverse         if (rev) {             mid = i + (j - i) / 2;             sum = i + j;             for (int x=i+1; x<=mid; x++)                 swap(pts[x], pts[sum-x]);         }         rev = !rev;         i = j;     }     for (i=0; i<n; i++)         if (pts[i] != NULL)             printf(" %d ", pts[i]->val); } int main() {     TreeNode* root = new TreeNode(1);     root->left = new TreeNode(2);     root->right = new TreeNode(3);     root->left->left = new TreeNode(4);     root->right->left = new TreeNode(5);     root->right->right = new TreeNode(6);     zigzag(root);     return 0; } 用普通的队列加标记即可实现。

用一个双端队列，即可解决，设一个标记位，记录上一层的遍历顺序，下一层遍历的时候相反方向遍历即可，同时修改标记位。

public static void snakePrint(BinaryTreeNode root) {         if(root == null) {             return;         }         ArrayDeque<BinaryTreeNode> arrayDeque = new ArrayDeque();         arrayDeque.add(root);         boolean flag = true;         while(!arrayDeque.isEmpty()) {             int size = arrayDeque.size();             if(flag) {                 for(int i=0;i<size;i++) {                     System.out.print(arrayDeque.peekFirst().value+" ");                     BinaryTreeNode tmp = arrayDeque.pollFirst();                     if(tmp.left != null) {                         arrayDeque.addLast(tmp.left);                     }                     if(tmp.right != null) {                         arrayDeque.addLast(tmp.right);                     }                 }                 flag = flag ? false : true;             } else {                 for(int i=0;i<size;i++) {                     System.out.print(arrayDeque.peekLast().value+" ");                     BinaryTreeNode tmp = arrayDeque.pollLast();                     if(tmp.left != null) {                         arrayDeque.addLast(tmp.left);                     }                     if(tmp.right != null) {                         arrayDeque.addLast(tmp.right);                     }                 }                 flag = flag ? false : true;             }         }     }