题目链接

LeetCode

题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

解题思路

层序遍历 + 双端队列

利用双端队列的两端皆可添加元素的特性，设打印列表（双端队列） tmp ，并规定：

  • 当前为奇数层 则添加至 tmp 尾部 ，
  • 当前为偶数层 则添加至 tmp 头部 。
  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     vector<vector<int>> levelOrder(TreeNode* root) {
  13.         if(root==NULL) return {};
  14.         deque<TreeNode*> dq;
  15.         vector<vector<int>> ret;
  16.         // 记录当前队列中的单双层
  17.         // true为单层，false为双层
  18.         bool flag = true;
  19.         dq.push_back(root);
  20.         while(!dq.empty()){
  21.             vector<int> ans;
  22.             int sz = dq.size();
  23.             if(flag){
  24.                 // 单层在双端队列的前面读取数据并将子结点在双端队列的后面插入队列
  25.                 // 先左节点后右结点
  26.                 while(sz--){
  27.                     TreeNode* node = dq.front();
  28.                     ans.push_back(node->val);
  29.                     dq.pop_front();
  30.                     if(node->left!=NULL) dq.push_back(node->left);
  31.                     if(node->right!=NULL) dq.push_back(node->right);
  32.                 }
  33.             }else{
  34.                 // 双层在双端队列的后面读取数据并将子结点在双端队列的前面插入队列
  35.                 // 先右节点后左结点
  36.                 while(sz--){
  37.                     TreeNode* node = dq.back();
  38.                     ans.push_back(node->val);
  39.                     dq.pop_back();
  40.                     if(node->right!=NULL) dq.push_front(node->right);
  41.                     if(node->left!=NULL) dq.push_front(node->left);
  42.                 }
  43.             }
  44.             ret.push_back(ans);
  45.             // 记录单双层
  46.             flag = !flag;
  47.         }
  48.         return ret;
  49.     }
  50. };
  • 时间复杂度 O(N) ： N 为二叉树的节点数量，即 BFS 需循环 N 次，占用 O(N) ；双端队列的队首和队尾的添加和删除操作的时间复杂度均为 O(1) 。
  • 空间复杂度 O(N) ： 最差情况下，即当树为满二叉树时，最多有 N/2 个树节点 同时 在 deque 中，使用 O(N) 大小的额外空间。