栈和队列遍历二叉树

栈和队列遍历二叉树

栈深度优先遍历

算法思想：

1、得到根结点后，若左孩子结点不空，不断地将当前结点的左孩子则入栈，第一步完成后，栈顶结点是叶结点 2、栈不空时，将栈顶元素弹出并保存到返回的答案数组，并查看当前结点是否有右孩子，有则入栈，然后重复步骤1。没有则接着执行步骤2，直到栈空。

class Solution {public: vector res; stack s; vector inorderTraversal(TreeNode* root){ if(root == nullptr) return res; TreeNode* cur = root; s.push(cur); //首先将所有的左孩子压栈 while(cur->left != nullptr){ s.push(cur->left); cur = cur->left; } //退出循环后cur指向叶结点，准备回溯 while(!s.empty()){ cur = s-(); res.push_back(cur->val); s.pop(); if(cur->right != nullptr){ s.push(cur->right); cur = cur->right; while(cur->left != nullptr){ s.push(cur->left); cur = cur->left; } } } return res; }};

递归解法

class Solution {public: vector res; vector inorderTraversal(TreeNode* root){ if(root == nullptr) return res; if(root->left != nullptr){ inorderTraversal(root->left); } res.push_back(root->val); if(root->right != nullptr){ inorderTraversal(root->right); } return res; }};

队列广度优先遍历

算法思想：

根结点入队后，然后将所有不为空的子结点入队每次循环进行操作时，都要同时处理一层的子结点，即将此时队列中所有结点的子结点全部入队，同时将当前处理完成的父结点出队

vector> levelOrder(TreeNode* root) { vector> res; if(root == nullptr){ return res; } queue q; q.push(root); while(!q.empty()){ vector temp; int count = q.size(); for(int i=1; i<=count; i++){ TreeNode* cur = q.front(); if(cur->left != nullptr){ q.push(cur->left); } if(cur->right != nullptr){ q.push(cur->right); } temp.push_back(cur->val); q.pop(); } res.push_back(temp); } return res; }

“之”字型打印结点

双端队列 + 层序遍历

遍历奇数层时：从队首出队，其子结点 先左后右从队尾入队遍历偶数层时：从队尾出队，其子结点 先右后左从队头入队

vector> levelOrder(TreeNode* root) { vector> res; if(root == nullptr){ return res; } deque dq; dq.push_back(root); bool isOdd = true; while(!dq.empty()){ vector layer; int len = dq.size(); // 奇数层 if(isOdd){ while(len-- > 0){ TreeNode* node = dq.front(); layer.push_back(node->val); dq.pop_front(); if(node->left != nullptr){ dq.push_back(node->left); } if(node->right != nullptr){ dq.push_back(node->right); } } }else{ while(len-- > 0){ TreeNode* node = dq.back(); layer.push_back(node->val); dq.pop_back(); if(node->right != nullptr){ dq.push_front(node->right); } if(node->left != nullptr){ dq.push_front(node->left); } } } res.push_back(layer); isOdd = !isOdd; } return res; }

N叉树的前序遍历

结点结构

class Node {public: int val; vector children; Node() {} Node(int _val) { val = _val; } Node(int _val, vector _children) { val = _val; children = _children; }};

递归版1

class Solution {public: vector res; void traverse(Node* root){ if(root == nullptr){ return ; } res.push_back(root->val); for(Node* node : root->children){ preorder(node); } } vector preorder(Node* root) { tranverse(root); return res; }};

递归版2

class Solution {public: vector res; vector preorder(Node* root) { if(root == nullptr){ return vector(); } res.push_back(root->val); for(Node* node : root->children){ preorder(node); } return res; }};

迭代版

class Solution {public: vector res; vector preorder(Node* root) { if(root == nullptr){ return res; } stack s; s.push(root); while(!s.empty()){ Node* cur = s-(); s.pop(); res.push_back(cur->val); for(int i = cur->children.size() - 1; i >= 0; i--){ s.push(cur->children[i]); } } return res; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。