阿里邮箱 wordpress,网站运营和seo的区别,浙江建设三类人员证书查询,做网站l价格给定一个二叉树#xff0c;返回其节点值的锯齿形层次遍历。#xff08;即先从左往右#xff0c;再从右往左进行下一层遍历#xff0c;以此类推#xff0c;层与层之间交替进行#xff09;。 例如#xff1a;给定二叉树 [3,9,20,null,null,15,7], 3/ \9 20/ \15 7返回… 给定一个二叉树返回其节点值的锯齿形层次遍历。即先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行。 例如给定二叉树 [3,9,20,null,null,15,7], 3/ \9 20/ \15 7返回锯齿形层次遍历如下 [[3],[20,9],[15,7]
] 首先我们想一下二叉树的层序遍历的思想 层序遍历的主要思路就是先把根节点存入然后输出输出的同时把根节点的左右孩子存入再把左孩子输出同样输出的同时把左孩子的孩子在存入直到遍历完成例如 a b c d e f g 先把a存入然后输出a输出a的同时把b c存入然后再输出b,输出b的同时存入d e继续输出c然后存入f g直到全部输出 //层序遍历
vectorint levelOrder(TreeNode *root) {vectorint answer;queueTreeNode *p;if (root nullptr) return answer;p.push(root);TreeNode* h nullptr;while (!p.empty()) {int size p.size();while (size--) {h p.front();answer.push_back(h-val);p.pop();//子树非空则压入队列 if (h-left ! NULL)p.push(h-left);if (h-right ! NULL)p.push(h-right);}}return answer;} 思路一对特定输入的结果进行反转输出 因为输出结果是第二层、第四层、第六层。。。的层序遍历结果反向输出可以在输出时将对应的行反转输出即可。 //蛇形遍历(反转)
vectorvectorint zigzagLevelOrder(TreeNode* root) {vectorvectorint answer;if (root nullptr) return answer;queueTreeNode *p;p.push(root);TreeNode* h nullptr;while (!p.empty()) {int size p.size();vectorint temp;while (size--) {h p.front();temp.push_back(h-val);p.pop();//子树非空则压入队列 if (h-left ! NULL)p.push(h-left);if (h-right ! NULL)p.push(h-right);}answer.push_back(temp);}for (int i 1; i answer.size(); i 2) {reverse(answer[i].begin(), answer[i].end());}return answer;
} 思路二利用双端队列 //蛇形遍历双端队列
vectorvectorint zigzagLevelOrder(TreeNode* root) {vectorvectorint answer;if (root nullptr) return answer;dequeTreeNode* deq;deq.push_back(root);int flag 0;int size 1;TreeNode *node nullptr;while (!deq.empty()) {vectorint vec;size deq.size();for (int i 0; i size; i) {node deq.front();deq.pop_front();//从左到右 if (flag % 2 0) {vec.push_back(node-val);}else {vec.insert(vec.begin(), node-val);}if (node-left ! NULL)deq.push_back(node-left);if (node-right ! NULL)deq.push_back(node-right);}answer.push_back(vec);flag;}return answer;
} 研究了一下双端队列后来发现改成队列就可以了。 class Solution {
public:vectorvectorint zigzagLevelOrder(TreeNode* root) { vectorvectorint answer; if (root nullptr) return answer; queueTreeNode* deq; deq.push(root); int flag 0; int size 1; TreeNode *node nullptr; while (!deq.empty()) { vectorint vec; size deq.size(); for (int i 0; i size; i) { node deq.front(); deq.pop(); //从左到右 if (flag % 2 0) { vec.push_back(node-val); } else { vec.insert(vec.begin(), node-val); } if (node-left ! NULL) deq.push(node-left); if (node-right ! NULL) deq.push(node-right); } answer.push_back(vec); flag; } return answer;
}
};
