广州网站建设报价单/企业信息查询

二叉树根据左子树、根节点和右子树的相对顺序分为三种遍历方式，这三种遍历方式可通过递归或者迭代（循环）的方式进行。**因为递归使用到的就是栈的思想，所以能够用递归方式实现的算法也能够通过迭代和栈的方式实现。**不过相对于迭代的方式，递归方式较为简单。同时，二叉树还有一种层次遍历方式。这几种遍历方式实现代码如下：

1.前序遍历

递归方式：

void preorder(TreeNode* root,vector<int>& vec){if (root != nullptr){vec.push_back(root->val);preorder(root->left, vec);preorder(root->right, vec);}}vector<int> preorderTraversal(TreeNode* root) {vector<int> ans;preorder(root, ans);return ans;}

迭代方式：

vector<int> preorderTraversal(TreeNode* root){vector<int> ans;stack<TreeNode*> stk;TreeNode* t = root;if (root == nullptr)return ans;elsestk.push(t);while (!stk.empty()){t = stk.top();stk.pop();ans.push_back(t->val);if (t->right != nullptr)stk.push(t->right);if (t->left != nullptr)stk.push(t->left);}return ans;}

2.中序遍历

递归方式：

void inorder(TreeNode* root, vector<int> &ans){if (root != nullptr){inorder(root->left, ans);ans.push_back(root->val);inorder(root->right, ans);}}vector<int> inorderTraversal(TreeNode* root) 
{vector<int> ans;inorder(root, ans);return ans;
}

迭代方式：

vector<int> inorderTraversal(TreeNode* root)
{vector<int> ans;stack<TreeNode*> stk;TreeNode* t = root;while (t != nullptr||!stk.empty()){while (t != nullptr){stk.push(t);t = t->left;}t = stk.top();ans.push_back(t->val);stk.pop();t = t->right;}return ans;
}

3.后序遍历

递归方式：

void postorder(TreeNode* root, vector<int> & vec)
{if (root != nullptr){postorder(root->left, vec);postorder(root->right, vec);vec.push_back(root->val);}
}vector<int> postorderTraversal(TreeNode* root) 
{vector<int> ans;postorder(root, ans);return ans;
}

迭代方式：

vector<int> postorderTraversal(TreeNode* root)
{vector<int> ans;stack<TreeNode*> stk;if (root == nullptr)return ans;elsestk.push(root);TreeNode* t = root;while (!stk.empty()){t = stk.top();stk.pop();ans.push_back(t->val);if (t->left != nullptr)stk.push(t->left);if (t->right != nullptr)stk.push(t->right);}reverse(ans.begin(), ans.end());return ans;
}

4.层次遍历–迭代方式

vector<vector<int>> levelOrder(TreeNode* root) 
{vector<vector<int>> ans;queue<TreeNode*> que;if (root == nullptr)return ans;elseque.push(root);TreeNode* t = root;while (!que.empty()){vector<int> sub;int size = que.size();for (int i = 0; i < size; ++i){t = que.front();sub.push_back(t->val);que.pop();if (t->left != nullptr)que.push(t->left);if (t->right != nullptr)que.push(t->right);}ans.push_back(sub);}return ans;
}