数据结构与算法面试题：实现二叉树的遍历（前序、中序、后序、层序）。
简介：数据结构与算法面试题：实现二叉树的遍历（前序、中序、后序、层序）。
算法思路
算法思路：
- 二叉树遍历是树的基础运算，主要包括前序遍历、中序遍历、后序遍历和层序遍历。其中，前序、中序和后序遍历即为深度优先搜索（DFS），而层序遍历则为广度优先搜索（BFS）。
- 对于遍历，我们可以使用递归或者迭代的方式来实现。递归方式比较直观，并且代码简单易懂；而迭代方式需要借助栈等数据结构，看上去比较复杂，但实际上在实际编程工作中也占有重要地位。
接下来给出C++实现的代码，注释详细：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> preorderTraversal(TreeNode* root) { // 前序遍历 vector<int> res; // 存储遍历结果的数组 stack<TreeNode*> stk; // 储存访问节点的栈 if (root != NULL) stk.push(root); // 将根节点压入栈 while (!stk.empty()) { // 在栈不为空时循环 TreeNode* p = stk.top(); // 取栈顶元素 stk.pop(); // 弹出栈顶元素 res.push_back(p->val); // 将当前节点的值加入到数组中 if (p->right != NULL) stk.push(p->right); // 先将右子节点压入栈 if (p->left != NULL) stk.push(p->left); // 再将左子节点压入栈中 } return res; } vector<int> inorderTraversal(TreeNode* root) { // 中序遍历 vector<int> res; // 存储遍历结果的数组 stack<TreeNode*> stk; // 储存访问节点的栈 TreeNode* p = root; while (p != NULL || !stk.empty()) { // 在有可访问的节点时循环 while (p != NULL) { // 一直沿左子节点走到最底端 stk.push(p); p = p->left; } p = stk.top(); // 取栈顶元素 stk.pop(); // 弹出栈顶元素 res.push_back(p->val); // 将当前节点的值加入到数组中 p = p->right; // 访问右子节点 } return res; } vector<int> postorderTraversal(TreeNode* root) { // 后序遍历 vector<int> res; // 存储遍历结果的数组 stack<TreeNode*> stk; // 储存访问节点的栈 if (root != NULL) stk.push(root); // 将根节点压入栈 while (!stk.empty()) { // 在栈不为空时循环（前序遍历的逆序） TreeNode* p = stk.top(); // 取栈顶元素 stk.pop(); // 弹出栈顶元素 res.insert(res.begin(), p->val); // 将当前节点的值插入数组的首部 if (p->left != NULL) stk.push(p->left); // 先将左子节点压入栈中 if (p->right != NULL) stk.push(p->right); // 再将右子节点压入栈 } return res; } vector<vector<int>> levelOrder(TreeNode* root) { // 层序遍历 vector<vector<int>> res; // 存储遍历结果的二维数组 queue<TreeNode*> q; // 实现BFS遍历的队列 if (root != NULL) q.push(root); // 将根节点加入队列 while (!q.empty()) { // 在队列不为空时循环 int size = q.size(); // 当前层的节点数目 vector<int> layer; // 存储当前层遍历结果的数组 for (int i = 0; i < size; i++) { // 遍历当前层的所有节点 TreeNode* p = q.front(); // 取出队头元素 q.pop(); // 弹出队头元素 layer.push_back(p->val); // 将当前节点值加入到当前层的数组中 if (p->left != NULL) q.push(p->left); // 如果有左子节点，加入队尾 if (p->right != NULL) q.push(p->right); // 如果有右子节点，加入队尾 } res.push_back(layer); // 将本层的遍历结果添加至最终输出结果中 } return res; } };
由于这是一道比较基础的二叉树问题，因此其实现思路也相对简单。但是在实际应用中需要灵活使用各种不同的遍历方式，并且代码的实现可能会涉及到栈和队列等相关数据结构。因此，熟悉常见的算法和数据结构、灵活掌握基础知识才是写好代码的关键。
- Java版本
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<Integer> preorderTraversal(TreeNode root) { // 前序遍历 List<Integer> res = new ArrayList<>(); // 存储遍历结果的数组 Stack<TreeNode> stk = new Stack<>(); // 储存访问节点的栈 if (root != null) stk.push(root); // 将根节点压入栈 while (!stk.empty()) { // 在栈不为空时循环 TreeNode p = stk.pop(); // 取栈顶元素 res.add(p.val); // 将当前节点的值加入到数组中 if (p.right != null) stk.push(p.right); // 先将右子节点压入栈 if (p.left != null) stk.push(p.left); // 再将左子节点压入栈中 } return res; } public List<Integer> inorderTraversal(TreeNode root) { // 中序遍历 List<Integer> res = new ArrayList<>(); // 存储遍历结果的数组 Stack<TreeNode> stk = new Stack<>(); // 储存访问节点的栈 TreeNode p = root; while (p != null || !stk.empty()) { // 在有可访问的节点时循环 while (p != null) { // 一直沿左子节点走到最底端 stk.push(p); p = p.left; } p = stk.pop(); // 取栈顶元素 res.add(p.val); // 将当前节点的值加入到数组中 p = p.right; // 访问右子节点 } return res; } public List<Integer> postorderTraversal(TreeNode root) { // 后序遍历 List<Integer> res = new ArrayList<>(); // 存储遍历结果的数组 Stack<TreeNode> stk = new Stack<>(); // 储存访问节点的栈 if (root != null) stk.push(root); // 将根节点压入栈 while (!stk.empty()) { // 在栈不为空时循环（前序遍历的逆序） TreeNode p = stk.pop(); // 取栈顶元素 res.add(0, p.val); // 将当前节点的值插入数组的首部 if (p.left != null) stk.push(p.left); // 先将左子节点压入栈中 if (p.right != null) stk.push(p.right); // 再将右子节点压入栈 } return res; } public List<List<Integer>> levelOrder(TreeNode root) { // 层序遍历 List<List<Integer>> res = new ArrayList<>(); // 存储遍历结果的二维数组 Queue<TreeNode> q = new LinkedList<>(); // 实现BFS遍历的队列 if (root != null) q.offer(root); // 将根节点加入队列 while (!q.isEmpty()) { // 在队列不为空时循环 int size = q.size(); // 当前层的节点数目 List<Integer> layer = new ArrayList<>(); // 存储当前层遍历结果的数组 for (int i = 0; i < size; i++) { // 遍历当前层的所有节点 TreeNode p = q.poll(); // 取出队头元素 layer.add(p.val); // 将当前节点值加入到当前层的数组中 if (p.left != null) q.offer(p.left); // 如果有左子节点，加入队尾 if (p.right != null) q.offer(p.right); // 如果有右子节点，加入队尾 } res.add(layer); // 将本层的遍历结果添加至最终输出结果中 } return res; } }
