代码随想录训练营Day15|层序遍历|226.翻转二叉树|101.对称二叉树 2

层序遍历（Carl给了十道题）

• 如何一层一层的保存节点？

• 借助队列结构，保存每一层保存过的元素，size记录当前层大小，决定当前层弹出多少元素；弹出一个元素，就在后续加入他的左右子元素；一层结束，size==0后，队列中全为下一层元素，此时更新size，开始进行该层的弹出，以及下一层的压入

• 代码实现：

  queue<TreeNode*> que;
  if(root != NULL) que.push(root);   //root不为空才加，为空不加
  //
  vector<vector<int>> result;
  
  //遍历
  while(!que.empyt()){   //中止条件，如果队列里面没有元素了，就遍历结束
      //首先记录当前层节点个数
      int size = que.size();
      //定义一维数组放当前层的元素
      vector<int> vec;
      //开始遍历当前层的元素
      while(size--){
          TreeNode* node = que.front();
          que.pop();
          //记录结果
          vec.push_back(node->val);
          //更新该节点的左右孩子
          if(node->left) que.push(node->left);
          if(node->right) que.push(node->right);
      }
      //将上面遍历一层得到的一维数组放到树的二维数组中
      result.push_back(vec);
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24

• 102.二叉树的层序遍历

  • 按上面的写一遍即可

• 107.二叉树的层次遍历II

  • 按上面的写一遍，然后反转result即可

• 199.二叉树的右视图

  • 右视图，也即只输出每一层最右边的一个，但是当右边许多为空时，也会输出位置在左边，但是顺序上是最右边的节点，因此每一个节点都要遍历到，只是对输出限制

• 637.二叉树的层平均值

  • 注意平均值是double类型
• 429. N叉树的层序遍历
  • 将压入queue节点的左右子节点，改为压入vector<Node*> Children中的所有节点

• 515.在每个树行中找最大值

  • 对每一层遍历到的数，取最大值即可

• 116.填充每个节点的下一个右侧节点指针

  • 每层最后一个指向NULL，我是让本节点指向下一个节点，在循环中设置最后一个节点的情况；Carl是让上一节点指向本节点，在循环中设置头结点的情况，循环结束后让最后的节点指向NULL

• 117.填充每个节点的下一个右侧节点指针II

  • 116题为完整二叉树，这题不是，但是代码一样不影响

• 104.二叉树的最大深度

  • 每一层只要遍历压入队列，记录该层是否存在节点即可，不用保存val

• 111.二叉树的最小深度

  • 叶子结点是左右都没有节点，应该是&&而不是||

226.翻转二叉树 （优先掌握递归)

• 接着上面的题目用层序遍历做了
• 在队列压入左右子节点时，将他们左右对调
• 注意左右子节点的调换和数组的调换不同，子节点不能同时指向一个节点，因此左右子节点要先赋值给temp1, temp2，然后将左右子节点指向nullptr，再分别赋值调换

101. 对称二叉树 （优先掌握递归）

• 按照左右子树是否可以相互翻转来做
• 需要收集子节点信息向父节点，因此使用后序遍历
• 这个递归函数输入的是用来比较的两个节点，还没遇到过，细品