扬州做网站公司,网站和微信同步建设,上海网站建设技巧,安阳区号是多少号码按之字形顺序打印二叉树
题目链接#xff1a;按之字形顺序打印二叉树
解题思路#xff1a;层次遍历#xff0c;借助队列
首先解决如何模仿之字形的问题#xff0c;我们为此设置一个flag#xff0c;每到一层就修改flag#xff0c;如果flag为true#xff08;初始为fals…按之字形顺序打印二叉树
题目链接按之字形顺序打印二叉树
解题思路层次遍历借助队列
首先解决如何模仿之字形的问题我们为此设置一个flag每到一层就修改flag如果flag为true初始为false的情况下就逆序一下数组。
其次解决如何间隔每一层的问题我们借助队列对实现队列是先进先出的线性表我们每一次让一层的节点进队列在下一次循环中让该层节点出队列同时让该层的子节点都进队列这样每次出队列的个数就是当前队列的大小下一层要出队列的个数就等于这一层的子节点进队列的个数也就是下一层的节点。由此每层的节点数等于进入该层时队列长度因为刚进入该层时这一层每个节点都会push进队列而上一层的节点都出去了。
具体做法 首先进行判空空树就返回空的res
其次建立辅助队列同时初始化flag变量根节点首先进入队列作为第一次循环中的temp。
每进入一层统计队列元素的个数同时修改flag的值每当访问一层该层的子节点一定都加入队列再下一层没加入因此此时队列中的元素个数就是这一层的元素个数 遍历这一层这么多的节点数出队加入到该层的数组中如果有子节点就让每个节点的子节点进队
访问完该层元素后根据flag的值决定该层对应的数组是否反转加入res中。
代码如下 vectorvectorint Print(TreeNode* pRoot) {TreeNode* head pRoot;vectorvectorint res;if(pRoot nullptr) return res;queueTreeNode* temp;//辅助队列temp.push(head);//根节点先进队TreeNode* p;bool flag true;//初始化flag标志位while (!temp.empty()) {//记录二叉树的某一行vectorint row;int n temp.size();flag !flag;//每进入一列更改标志位for(int i0; in; i){p temp.front();temp.pop();row.push_back(p-val);//有子节点进队这样上一层出队下一层进队保证了队列大小就是下一层节点个数if(p-left) temp.push(p-left);if(p-right) temp.push(p-right);}if(flag) reverse(row.begin(), row.end());//反转数组模仿之字形的遍历效果res.push_back(row);//将该层放入结果数组中} return res; }解题思路2借助栈
元素反转我们很容易想到栈我们在此借助两个栈来实现之字形输出
首先栈1实现正序的层的元素输出这样就要求我们在逆序输出的层中先让右子树进栈再让左子树进栈反之对于下一层需要逆序输出的我们就先让左子树进栈再让右子树进栈
具体步骤 首先判空空树返回空的res
建立两个辅助栈根节点先进入栈1
当某个栈不空的时候我们进入循环在循环中让下一层子树进入到相应的栈中让该栈该层元素进入数组中最后如果数组不空就加入最后结果集中
根据访问的次序栈1放入的是奇数层也就是正常顺序输出的层在该层中让该层的子树按照先左后右的顺序加入栈2这样在访问栈2的元素的时候就是按照逆序访问的偶数层相反在访问栈2时将栈2中节点的子树按照先右后左的顺序加入栈1中这样再访问栈1的时候就是按照 先左再右的顺序访问了
每次访问完一层即一个栈为空则将一维数组加入二维数组中并清空数组以便下一层用来记录需要注意的是将temp数组加入结果集res中一定要注意temp是否为空因为存在一次外层循环只有一个栈在其中放入元素的情况
代码如下 vectorvectorint Print(TreeNode* pRoot) {TreeNode* head pRoot;vectorvectorint res;if(head nullptr) return res;stackTreeNode* s1;stackTreeNode* s2;s1.push(head);while(!s1.empty() || !s2.empty()){vectorint temp;while(!s1.empty()){TreeNode* node s1.top();temp.push_back(node-val);if(node-left) s2.push(node-left);if(node-right) s2.push(node-right);s1.pop();}if(temp.size()) res.push_back(temp);temp.clear();while(!s2.empty()){TreeNode* node s2.top();temp.push_back(node-val);if(node-right) s1.push(node-right);if(node-left) s1.push(node-left);s2.pop();}if(temp.size()) res.push_back(temp);}return res;}
