数据结构与算法面试题：实现二叉树的遍历（前序、中序、后序、层序）。

素颜马尾好姑娘i 2024-03-16 17:08 16阅读 0赞

## 数据结构与算法面试题：实现二叉树的遍历（前序、中序、后序、层序）。 ##

简介：数据结构与算法面试题：实现二叉树的遍历（前序、中序、后序、层序）。

### 算法思路 ###

算法思路：

*  二叉树遍历是树的基础运算，主要包括前序遍历、中序遍历、后序遍历和层序遍历。其中，前序、中序和后序遍历即为深度优先搜索（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;
        }
    }