02、二叉树层序遍历

厨子大约 3 分钟数据结构算法基础面试题解析二叉树遍历程序厨校招社招算法题精讲

层序遍历

顾名思义,一层一层的遍历.

比如刚才那棵二叉树的层序遍历序列即为 1 ~ 9.

二叉树的层序, 这里我们需要借助其他数据结构来实现, 我们思考一下, 我们需要对二叉树进行层次遍历, 从上往下进行遍历, 我们可以借助什么数据结构来帮我们呢 ?

我们可以利用队列先进先出的特性，使用队列来帮助我们完成层序遍历, 具体操作如下

让二叉树的每一层入队, 然后再依次执行出队操作,

对该层节点执行出队操作时, 需要将该节点的左孩子节点和右孩子节点进行入队操作,

这样当该层的所有节点出队结束后, 下一层也就入队完毕,

不过我们需要考虑的就是, 我们需要通过一个变量来保存每一层节点的数量.

这样做是为了防止, 一直执行出队操作, 使输出不能分层

好啦,下面我们直接看动画吧,

测试题目: leetcode 102 二叉树的层序遍历

Java Code:

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {

      List<List<Integer>> res = new ArrayList<>();
      if (root == null) {
          return res;
      }
      //入队 root 节点，也就是第一层
      Queue<TreeNode> queue = new LinkedList<>();
      queue.offer(root);
      while (!queue.isEmpty()) {
          List<Integer> list = new ArrayList<>();
          int size = queue.size();
          for (int i = 0; i < size; ++i) {
              TreeNode temp = queue.poll();
              //孩子节点不为空，则入队
              if (temp.left != null)  queue.offer(temp.left);
              if (temp.right != null) queue.offer(temp.right);
              list.add(temp.val);
          }
          res.add(list);
      }
      return res;
    }
}

C++ Code:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
      vector<vector<int>> res;
      if (!root) return res;
      queue<TreeNode *> q;
      q.push(root);
      while (!q.empty()) {
          vector <int> t;
          int size = q.size();
          for (int i = 0; i < size; ++i) {
              TreeNode * temp = q.front();
              q.pop();
              if (temp->left != nullptr)  q.push(temp->left);
              if (temp->right != nullptr) q.push(temp->right);
              t.emplace_back(temp->val);
          }
          res.push_back(t);
      }
      return res;
    }
};