IT评测·应用市场-qidao123.com技术社区

标题: 力扣103.二叉树的锯齿形层序遍历 [打印本页]
作者: 麻花痒    时间: 2025-4-14 13:16
标题: 力扣103.二叉树的锯齿形层序遍历
题目描述

题目链接103. 二叉树的锯齿形层序遍历
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间瓜代进行）。
示例 1：


  1. <strong>输入：</strong>root = [3,9,20,null,null,15,7]
  2. <strong>输出：</strong>[[3],[20,9],[15,7]]
复制代码
示例 2：
  1. <strong>输入：</strong>root = [1]
  2. <strong>输出：</strong>[[1]]
复制代码
示例 3：
  1. <strong>输入：</strong>root = []
  2. <strong>输出：</strong>[]
复制代码
提示：

思路解析

        与层序遍历雷同，值必要在偶数层将所取出的val值数组反转再存入答案数组中
        利用一个队列进行每层的节点存储，当队列中有元素时，遍历该队列，取出val值并将该节点的左右子节点放入队列，末了弹出该节点
        必要注意的是，在遍历队列的时候，判断语句不能是队列的empty函数。由于每个元素还会放入子节点，以是在遍历前应当创建一个int变量进行存当前队列巨细，再用队列巨细进行遍历
代码实现

  1. class Solution {
  2. public:
  3.     vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
  4.         if(root==nullptr)return {};
  5.         int cnt = 1;//层数
  6.         vector<vector<int>>ans;
  7.         queue<TreeNode*>que;//记录每一层的节点
  8.         que.push(root);//第一层节点
  9.         while(que.size()){//当该层还有元素则进入循环
  10.             vector<int>vec;//记录该层节点的val值
  11.             int n=que.size();
  12.             while(n--){//取出val值，从左至右放入下一层元素
  13.                 vec.push_back(que.front()->val);
  14.                 if(que.front()->left)que.push(que.front()->left);
  15.                 if(que.front()->right)que.push(que.front()->right);
  16.                 que.pop();
  17.             }
  18.             if(cnt%2==0)reverse(vec.begin(),vec.end());//如果该层为双数层，反转数组
  19.             ans.push_back(vec);//把该层val值数组放入答案数组中
  20.             cnt++;//该层处理完成后层数加一
  21.         }
  22.         return ans;
  23.     }
  24. };
复制代码


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/) Powered by Discuz! X3.4