2022-09-22-阿里云一面-60min

时间：9点 - 10 点
四十几才写代码，10点还要面微软，急了，差点没写出来，最后写出来的连队列都没用了，简单粗暴。。
问了很多开放性的问题包括团队协作啥的，做完后还继续问了几个，问满了这六十分钟。

/*
 * 题目：按层交替方向遍历二叉树
 * 样例：下面是一颗二叉树：
 *
 *            A
 *      B          C
 *   D    E     F      G
 *  H I  J K   L M    N O
 *
 * 遍历输出： A C B D E F G O N M L K J I H
 */
struct Node {
    int value;
    struct Node* left;
    struct Node* right;
};

void Traverse(struct Node* root, vector<int>& output)
{
      if(!root) return;
      printf("%c ", root->value);
    vector<Node*> q;
      q.push_back(root);
      bool ltor = false;
      while(q.size()){
          vector<Node*> next;
          for(auto& t:q){
            if(t->left)
                next.push_back(t->left);
            if(t->right)
                next.push_back(t->right);
        }
          if(ltor){
             for(auto& i:next)
              printf("%c ", i->value);
        }else{
              for(int i=next.size()-1;i>=0;i--)
              printf("%c ", i->value);
        }
          q=next;
          ltor=!ltor;
    }
}

2022.09.23 午夜随笔~大材小用，自然会变得简单

昨天阿里云一面那个层次交叉遍历，面试时用队列没做出来，改成了数组粗暴层次遍历再判断方向；洗澡时想到用栈实现。
一看题解，醉了，还可以用双端队列模拟栈，从能力最小最适合角度优先讲，栈<双端队列<动态数组，用栈最合适。
面试时用了最大能力的数据结构，自然就好做出来。

吗？

https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/solution/neng-bu-neng-yong-zhan-shi-xian-ni-by-sw-0vrz/