算法与数据结构面试题-2

常见面试题

1. 说说满二叉树和完全二叉树？⭐⭐⭐⭐⭐

   二叉树还有两种特殊形式， 一个叫作满二叉树， 另一个叫作完全二叉树。

   一个二叉树的所有非叶子节点都存在左右孩子， 并且所有叶子节点都在同一层级上， 那么这个树就是满二叉树。

   完全二叉树的条件没有满二叉树那么苛刻： 满二叉树要求所有分支都是满的； 而完全二叉树只需保证最后一个节点之前的节点都齐全即可。

2. 说说树的遍历有几种方式？⭐⭐⭐⭐⭐

   树的遍历有四种，前序遍历、中序遍历、后序遍历、层序遍历。

   区别在于访问节点的顺序不同：前序遍历（根-->左-->右）、中序遍历（左-->根-->右）、后序遍历（左-->右-->根）、层序遍历（按层从左至右访问）

3. 用栈实现一下树的前序遍历，说说思路⭐⭐⭐⭐⭐

   前序遍历，口诀很好记：根-->左-->右。所以根节点先入栈并输出。然后访问左子树，打印完左节点出栈。

   根-->左访问完了，开始访问右，因为我们的栈顶保存了根节点，通过获取栈顶元素，也就可以访问根节点的右边了，所以此时获取根节点后，让根节点出栈。

   重复以上的步骤。直到栈为空，整棵树也就完成输出了。

   class Solution {
   public:
       vector<int> preorderTraversal(TreeNode* root) { // 前序遍历，口诀很好记：根-->左-->右。
           vector<int> res;
           if (root == nullptr) {
               return res;
           }
   
           stack<TreeNode*> stk;
           TreeNode* node = root;
           while (!stk.empty() || node != nullptr) {
               while (node != nullptr) {
                   res.emplace_back(node->val); // 前序遍历，先访问根
                   stk.emplace(node);      
                   node = node->left;           // 接下来进入左子树
               }
               if (!stk.empty()){
                   node = stk.top();
                   stk.pop();
                   node = node->right;          // 接下来进入右子树
               }
           }
           return res;
       }
   };
   // 时间复杂度：O(n)
   // 空间复杂度：O(n)
   

4. 用队列实现树的层序遍历，说说思路？⭐⭐⭐⭐⭐

   层序遍历，就是一层一层按顺序访问节点。所以根节点先入队列并输出，输出完就要让根节点出队列。然后就判断根节点是否有左右子节点，如果有，就让左右子节点入队列。

   接下来就是依次取队列前面的元素了，取出子节点，让子节点出队并输出子节点，然后判断子节点是否有左右子节点，如果有，就让左右子节点入队列。

   又取出剩余子节点，重复以上步骤，直到队列没有元素可取了，此时整棵树也输出完毕了。

   class Solution {
   public:
       vector<vector<int>> levelOrder(TreeNode* root) {
           if (root == NULL) return {};
           queue<TreeNode*> que;            // 创建队列
           que.push(root);                  // 根节点先入队
           vector<vector<int>> res;
           while (!que.empty()){
               vector<int> vec;
               int len = que.size();
               for (int i=0; i<len; i++){
                   TreeNode* node = que.front();
                   vec.push_back(node->val);                       // 访问根节点
                   que.pop();                                      // 根节